acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 最详细 CDQ 分治题解

    这是一道二维平面的数点,同时也加上了时间。做过动态逆序对的可能会记得对于 k 维平面、动态加点和询问的题目,可以将时间也当作一个维度,计算 x 轴、 y 轴、时间都更小的点。由于二维平面不可能所有点都在当前点的左下角,所以我们将图掉转做4次 CDQ, 因为是曼哈顿距离,所以用树状数组维护 x+y 的最大值,用询问点的 x+y 减去最大的 x+y 即可,掉转需要计算最大 x 值和 y 值,注意最后要 +1 因为掉转时 x/y 最大的那个点如果掉成 0 树状数组会爆。输入也要+1因为坐标最小为0. 以下是代码:

    userId_undefined
    Xylophone
    时间刺客空间掌握者时空双修者荣耀黄金传道者CSP-J一等奖
    4阅读
    0回复
    2点赞
  • CDQ分治

    没用快读快写82ms,目前全ACGO跑的最快

    userId_undefined
    zby_114514
    时间刺客空间掌握者时空双修者秩序白银
    16阅读
    3回复
    1点赞
  • 要用ll和快速输入/输出流

    如标题

    userId_undefined
    xxb
    出道萌新时间刺客空间掌握者时空双修者模拟·模拟练习生秩序白银
    18阅读
    1回复
    1点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页