P4514 上帝造题的七分钟

· · 题解

分治套扫描线

不开 O2 可过。

前言

二维树状数组的模板，但是这篇题解不讲二维树状数组。

感谢 H_Kaguya 和 yllcm 指教扫描线相关问题。

前置知识：差分、线段树、树状数组、扫描线、分治。

线段树和扫描线

使用扫描线、线段树和差分离线解决静态问题：平面加之后平面求和。

扫描线的收益：问题降一维，维护一个一维线段树即可。

扫描线的代价：问题转为在线，所以扫描线只能用一次。

将修改和查询按照某个坐标轴差分成两个平面修改或平面查询（将矩形拆成两个等长对边），本文中扫描线全部按 y 轴差分且按照 y 轴坐标从小到大扫描。

为保证答案正确，差分时将询问中高度较小一边高度 -1，修改中高度较大一边高度 +1，等高度的情况先执行修改操作。

使用两次扫描线，第一次扫描时直接执行修改，在查询时将贡献乘以该查询的 y 轴坐标 +1（查询的 y 轴坐标修改后可能是 0，两次统计时线段树中的信息可能不等），同一查询先减后加。第一次扫描线的修改如果全部执行，线段树会自行清空。第二次扫描时将修改的贡献乘以其 y 轴坐标，同一查询先加后减，线段树不会清空这次扫描的修改，差分后的修改带了高度权值。

可以感性理解为第一次统计查询范围内“不完整”的矩形，第二次统计查询范围内“完整”的矩形并且去掉第一次扫描加入的多余贡献。

时间复杂度 O(n\log n)。

Code：扫描线解决静态二维平面加平面求和。

写得这么多是因为网上没有多少文章讲这个，至少笔者学习的时候没有找到。

分治和常数优化

这道题并非静态问题，但分治可以做到化动为静，需要离线处理。

按照时间顺序划出分治线，处理分治线左侧修改操作对分治线右侧查询操作的贡献即可，扫描线的使用方法上文已经讲了。关于分治，具体解释和使用方法可以看 OI Wiki，需要注意的是不能重复统计贡献，而且要按时间顺序进行操作。

分治执行 \log n 层，时间复杂度 O(n\log^2 n)。

注意在第二次扫描之后清空数据结构。

Code：朴素代码，询问和修改使用了同样的结构体。评测记录，吸氧可过。

但是如果要吸氧才能通过，这篇文章就没有意义了，为什么不写正解呢？我自己推不出来正解的式子。

开始优化，注意到三个能够优化的细节：分治过程中多次对同一操作差分、分治过程中重新排序、线段树需要开 long long。

常数瓶颈应该在排序。考虑使用归并优化。分治线左边的操作无论如何都比右边的查询更早执行，可以先递归左半边和右半边，扫描线，归并左右区间。

然而操作差分之后才能排序。

把操作差分之后再分治不就行了？很遗憾，扫描线的过程中，同一个查询或修改操作差分后不能分开。

类似 FFT，分治总长度为 2 的整数次幂时分治树为完美二叉树，同一个操作差分后不会分开，同时由于分治长度为 2 时必定属于同一操作，自然满足排序条件，递归层数可以减少一层。用空操作填充序列直到总长度为 2 的整数次幂即可。

另外只有区间内同时存在修改和查询时才会影响答案，这可以用前缀和判断。

Code：此时的代码已经能通过六个测试点。

最后的瓶颈是线段树，改为区间加区间求和的树状数组之后可以通过题目，树状数组可以不开 long long 从而获得更小的常数。

AC Code：评测记录。

一个未使用的优化：由于补齐了序列，可以将分治改为倍增。

总结

效率比正解差，也许读者会认为这种解法不是很值得学习，但是它也有二维树状数组没有的优点。

本题虽然是针对二维树状数组设计的，但分治套扫描线的解法也适用，并且这种离线分治的方法在更大的数据范围下表现会更好。

闲话

当初写这种解法的时候，没有打算通过，一步步优化后却取得了意料之外的成果，十分令人欣喜。

题解区没有这种做法，也许是认为效率太差？笔者认为能够不开 O2 优化通过已经足够，毕竟题目的数据范围较小，操作较多，树状数组以外的做法很难胜任。

虽然思路早就有了，但实现花费了很长时间，积累了宝贵的经验。