RainAir
My OI Blog
RainAir
「ZROI849」 大厦

题目描述:给你若干条形如 $x+y=c$ 或 $x-y=c$ 的直线,这些直线与坐标轴的夹角是 45 度,问在矩形 $(0,0) \to (W,H)$ 中,有多少个子矩形。
图片示意:
https://blog.aor.sd.cn/wp-content/uploads/2019/07/2.png
上图有 $19$ 个子矩形。
$n \leq 10^5$
首先这一题目 $O(n^3)$ 的复杂度十分好做:就是枚举三条边 去 map 找一下第四条边就好了。
我们考虑如何做到 $O(n^2logn)$:我们可以考虑先旋转坐标系,这样就是处理横着的和竖着的线了。
我们来考虑一下如何旋转坐标系:我们首先考虑将斜率为负的直线旋转到垂直方向上,那么斜率为正的直线就旋转到水平方向上了。考虑对于原来的一个点 $(x,y)$ ,旋转后变为 $\left(\frac{x+y}{\sqrt{2}},\frac{x-y}{\sqrt{2}}\right)$,但是我们发现有个$\sqrt{2}$很烦,所以我们令新坐标系的单位为 $\sqrt{2}$,旋转后的坐标也就是 $(x+y,x-y)$。
我们考虑枚举两条竖着的线,这样就能二分出有多少条横着的直线同时经过这两条竖线,记这样的横线的数量为 $a$,这两条竖线对答案的贡献就是 $\left(^a_2\right)$。
我们考虑如何在 $O(nlogn)$ 的时间内完成该题:考虑暴力枚举第 $i$ 条竖线后,记竖线 $i$ 和 $j$ 共同交的横线数量为 $cnt_{j}$,则我们需要统计:
$$\sum_{j = i+1}^n \left(^{cnt_{j}}_ 2\right)$$
我们考虑如何优化这个式子:我们先将竖线的 x 坐标和横线的左端点拿出来排序,然后使用扫描线思想,如果扫到了一条横线,那么在这条横线 $[l,r]$ 之间的所有竖线对的 $cnt$ 都会 $+1$,所以我们遇到横线就加一下前缀,然后对于竖线查询就需要快速统计一下上面的式子。
现在问题相当于转化为:需要实现一个数据结构 满足操作区间加,区间询问 $\sum_{i=l}^r \left(^{a_i}_ 2\right)$
我们对于线段树的每一个节点,维护区间和和组合数和。我们考虑单点 $+k$ 后对答案的贡献:
$$\left(^{x+k}_ 2\right) = \left(^x_2\right) + \left(^k_2\right) + xk$$
证明就是考虑组合意义,从 $x+k$ 个球中选出 $2$ 个,方案有全选 $[1,x]$ 之间的物品,全选 $[x+1,k]$,选一个 $[1,x]$ 和一个 $[x+1,k]$。
所以我们套个区间操作:
\begin{align*}
\sum_ {i=l}^r \left(^{a_i+k}_ 2 \right) &= \sum_ {i=l}^ r \left(^{a_i}_ 2 \right)+k a_ i+\left(^k_ 2\right) \\
&=\sum_ {i=l}^r \left(^{a_ i}_ 2\right) + k\sum_ {i=l}^r a_ i + (r-l+1)\left(^k_ 2\right)
\end{align*}
所以维护区间和和区间组合数和,优先更新组合数就好了。
于是这个题就做完了。注意需要离散化+取模就可以了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/698
如文中无特殊声明,本文采用 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

「ZROI849」 大厦
题目描述:给你若干条形如 $x+y=c$ 或 $x-y=c$ 的直线,这些直线与坐标轴的夹角是 45 度,问在矩形 $(0,0) \to (W,H)$ 中,有多少个子矩形。 图片示意: 上图有 $19$ 个子矩形。 $n \leq…
扫描二维码继续阅读
2019-07-17
标签
近期评论