处理带限制的点 ​

问题描述 ​

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