处理带限制的点

问题描述

很多 DS 问题最终会转化成一个很基本的问题：点的问题。常见的是：统计点数（能差分）/最优化点权（不能差分）。同时，问题会对合法的点进行抽象定义。那么，问题的难点就在于将抽象的合法限制以优的复杂度实现。

常识

静态的 k 维问题的复杂度一般为 $log^{(k - 1)}$ 。
动态的 k 维问题的复杂度一般为 $log^k$ 。

整体思路

核心：用尽可能少的 $log$ 刻画出限制。有时，你容易提出一个 $log$ 特别多的限制办法，这时重点就是想办法减少限制。

对限制的具体处理思路

处理修改

将时间维看成一维限制处理：查询看成是对时间维的前缀修改点查询。
直接在线修改处理。

处理偏序（单限制不等式）

离线：扫描线（即 CDQ 的一维形态），CDQ 分治。离线带修可以将时间维看作一维限制。
在线不带修：序列上可持久化结构（例如主席树）。
在线带修：树状数组。

处理一般不等式

尝试套用偏序做法：
- 可以差分：差分后套偏序做法。
- 扫描线可以结合带修 DS 使用。
- 一般的：分治套偏序做法。
树套树：
- 一维形态：线段树。
- BIT 套 SGT：一维偏序，一维双向。
- SGT 套 SGT（二维线段树）：两维双向。
K - D tree

注意

优先考虑离线做法，在线做法时空比较劣。
并不一定要用时间维分析，因为时间维将修改操作一般化了，失去了特殊性。

处理限制的思考技巧

一般化表示比较复杂，可以简单分类讨论：情况变多了，但单个情况的条件变少了，去除了冗余条件。
灵活转化/分裂/合并偏序限制和一般限制：
- 一般限制可以拆分成上下界的偏序限制。特别的，可差分的问题可以直接去掉一般限制。
- 有时，多个偏序限制可以合并成一个一般限制。
询问和点贡献方式互换：有时询问贡献点更好处理，就要交换。
其他的思考技巧就和分析性质相似了。

典例

区间 mex

显然二分，问题就变成： $<=lim$ 的所有数是否都在 $[l, r]$ 中出现。
出现可以刻画成：对于 $x$ 的所有出现位置 $pos$ ，存在 $l <= pos <= r$ 。
拆偏序处理，那么 $pos <= r$ 直接扫掉，条件就转化成 $max(pos) >= l$ 。

给定若干区间 $[l_i, r_i]$ 以及对应权值 $c_i$ ，多次询问和 $[l, r]$ 的交 $>= k$ 的区间的最小权值

直接分析的话可以列出一堆条件，非常麻烦，考虑减少条件数。
有交这个一般条件刻画复杂，考虑分类讨论：
- 完全包含，完全被包含，包含左端点，包含右端点。
- 完全包含可以被最后两个替代，只剩三种情况。
- 最后两个都是好做的，即二维偏序。
- 完全被包含需要对长度和左右端点做限制，即： $l <= l_i$ ， $r_i <= r$ ， $r_i - l_i + 1 >= k$ 。
- 这并不足以通过，考虑再次优化条件。
- 发现前两个偏序可以合并成对 $r_i$ 的双向限制，那么扫偏序再线段树处理双向限制即可。

区间查询前驱

问题刻画：
- 每个点 $(pos, val)$ 。
- $lim$ ： $l <= pos <= r$ ， $val <= x$ 。
- $aim$ ： $maximum(val)$ 。
离线静态做法：观察到限制形态，直接扫描掉偏序，剩下的用 SGT。
离线动态做法：
- 将时间维也刻画出来：每个点 $(t_l, t_r, pos, val)$ ，询问 $(t, l, r, x)$ 。
- $lim$ ： $t_l <= t <= t_r$ ， $l <= pos <= r$ ， $val <= x$ 。
- $aim$ ： $maximum(val)$ 。
- 一个办法是把一般不等式拆掉，应该是 $log^3$ 。
- 考虑直接树套树，扫 $val <= x$ ，剩下的线段树套线段树。
在线动态做法：树套树可以直接修改，这里将 $val <= x$ 作 BIT 那一维可能会更方便。

矩形加矩形查和

首先肯定差分，将矩形查差分成前缀矩形查（键值只有单点了）。
考虑一下矩形加的差分，本来想也这么差，但是不太好贡献，可以差成：后缀矩形加。
考虑一个点 $(x, y, v)$ $(x, y, v)$ 对一个询问 $(q_x, q_y)$ $(q x , q y )$ ：
- $lim$ ： $x <= q_x$ ， $y <= q_y$ 。
- 贡献： $(q_x - x + 1) * (q_y - y + 1) * v=( (q_x + 1) * (q_y + 1) - (x * (q_y + 1)+y * (q_x + 1)) + x * y ) * v$ 。
- 直接维护四个二维偏序即可，可以在线或离线，都是 $log$ 。

先做矩形加，然后做矩形查最值

限制是二维的双向不等式，而且求最值不能差分。
树套树显然没有前途，主要是 tag 不好处理。
可以考虑分治，每次处理跨过中线的询问，然后将右半部分去掉。
首先考虑偏序做法，显然可以差分以后历史最值，那么直接套用即可。

区间加、区间撤销上次加、单点查值（ $1e5$ 级别）

可以看成每个点都有一个栈，每次可以区间 push 和区间 pop，然后单点查栈中和。
线段树完蛋，看看根号做法，也不太行，因为撤销受限于时间顺序。
那么得转化一下，加上时间维。
但是注意操作有时间顺序，用不等式刻画有点问题，所以画出平面来考虑。
发现区间操作就是一条竖线，单点查值就是查横的线，从左到右看的。
考虑竖着扫，维护每个时间点对应的答案，每次查前缀。
容易发现这个可以类似括号匹配，区间维护已经匹配剩下的 ))))((((。
而右括号只要维护个数，左括号需要维护所有的值。
直接维护理论可行，但是还有单点修改以及前缀查，我们需要快速实现：
- 删掉一段后缀左括号。
- 拼接两段左括号。
- 整段查询左括号对应的权值和。
好像只能平衡树，而且每个点都要存，所以要可持久化。