一月题目总结

P6109 rqrmq1

https://www.luogu.com.cn/problem/P6109

这个题有很多精妙，经典的操作。非常精彩。

首先第一个经典的是，遇到二维平面就考虑扫描线。然后变成一段时间内的最大值问题后，就很自然的想到，用猫树的思想，把一段时间拆成前后缀，从而变成历史问题。

关于这类，离线后维护另一个可撤销数据结构的题（整体二分中也很常见），都有一个问题值得设计，就是这个区间内的指针如何移动，这一点直接影响程序的好写程度和常数

第二个非常非常妙的，就是关于差分。如果差分 l 和 r+1 处，就会有很多很多数不清的细节，关键原因还是，我们的 pos 左右移动，但是我们的差分设计的却不对称。

游队的超级智慧idea：把差分塞到缝里面，每一列维护左缝和右缝即可。实际上，把每一列的+val或-val升序排序，隐式维护即可。