RainAir
My OI Blog
RainAir
「SHOI2007」园丁的烦恼

题目描述

题目链接

平面上有 $n$ 个点 $(x_i, y_i)$,$m$ 次询问,每次询问为一个矩形内有多少点。 允许离线。

其中 $ n,m \leq 500000 $。

解题报告

首先这个东西显然可以二维前缀和来预处理。

具体来说就是设这个前缀和数组为 $S$,每次暴力预处理,暴力查询矩形就可以了。

每次查询矩形$(a,b),(c,d)$:$ans=S(c,d) – S(a,d) – S(b,c) + S(a,b)$。

时间复杂度是 $O(n^2)$,无法接受。

让我们考虑扫描线。

形式化来讲,我们不管是查询还是树的位置都看作一些点,然后将所有询问离线,以 $x$ 坐标为关键字排序。这样我们将其降维了。

这样降维之后可以看成两种操作:

  • 插入一个点
  • 询问答案

可以用树状数组维护。

具体来说,树状数组维护的是 $y$ 坐标为 $[0,y]$ 的点的个数(这个显然是可减的,类似于前缀和),然后扫一遍这些点,遇到代表树的点先将其扔进树状数组里,遇到每个询问就按照上面的式子直接对关于的 $y$ 坐标询问就可以了。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/58
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「SHOI2007」园丁的烦恼
题目描述 题目链接 平面上有 $n$ 个点 $(x_i, y_i)$,$m$ 次询问,每次询问为一个矩形内有多少点。 允许离线。 其中 $ n,m \leq 500000 $。 解题报告 首先这个东西显然可以二维前…
扫描二维码继续阅读
2018-10-01
标签
近期评论