今天（2023.3.7）上午 大聪明 LgxTpre 问我区间 reverse 全局 kth 怎么做，我以为他问的是 区间 reverse 区间 kth，确认了一下问题才发现他降智了区间 reverse 根本不会改全局 kth，然后现在出现了新的问题，区间 reverse 区间 kth 怎么做......
我想了一会儿发现不会 polylog，下午 LgxTpre 在 U 群里问了一下，lxl 说能归约到矩阵乘法，但是一直在魔怔没说明白咋归约，142857cs 老师一言切綮，我自己想了想完善了下细节。
阅读之前请先确认，归约的不严谨的定义，以免搞混了方向。问题 A 归约到问题 B，说的是 A 的特殊情况能够对应到 B 的一般情况，那么解决了问题 A 就解决问题 B，也就是问题 A 会不弱于问题 B．
一
区间删除，可撤销，全局查询 \(=x\) 的个数。
现在有三个 \(\mathcal{O}(\sqrt n)\times \mathcal{O}(\sqrt n)\) 的 01 矩阵 \(A,B,C\)，其中 \(C=AB\)．
序列分块，\(B_{j,k}\) 为第 \(j\) 个块是否有 \(k\)，很容易通过给定特殊的序列来构造出任意的 \(B\)．
\(A_{i,j}\)：第 \(i\) 波操作中第 \(j\) 个块是否未被删除。
在第 \(i\) 波操作中，先用 \(\mathcal{O}(\sqrt n)\) 次操作删除掉该删除的块，然后询问一遍 \(1,2,3,\cdots,\mathcal{O}(\sqrt n)\) 的出现次数，再撤销掉 \(\mathcal{O}(\sqrt n)\) 删除。这样一共用了 \(\mathcal{O}(\sqrt n)\) 次操作，可以构造出任意的 \(A_{i,\sim}\)，以及询问所有的 \(C_{i,\sim}\)．
区间删除，可撤销，全局 kth，也一样，通过询问一遍 \(1,2,3,\cdots,\mathcal{O}(\sqrt n)\) 的 kth，差分之后就是 \(1,2,3,\cdots,\mathcal{O}(\sqrt n)\) 的出现次数，所以也能用上面那个归约到 \(\mathcal{O}(\sqrt n)\times \mathcal{O}(\sqrt n)\) 的 01 矩阵乘法。然后区间 kth 自然不弱于全局 kth，于是现在有了：
“区间删除，可撤销，区间 kth” 归约到 “\(\mathcal{O}(\sqrt n)\times \mathcal{O}(\sqrt n)\) 的 01 矩阵乘法”。
二
现在来完成下面几个问题：
- 区间加，区间（全局亦可） \(\leq x\) 的个数。
\(\leq x\) 减去 \(\leq (x-1)\) 的就是 \(=x\) 的个数，然后用区间加/减 \(+\infty\) 来实现区间删除，以及删除操作的撤销。从而归约到区间删除，可撤销，全局 \(=x\) 的数的个数。
这里甚至只能加正数都可以，只需要让第 \(i\) 波问的是 \((i-1)\times inf+x\) 就行，是 \(>i\times inf\) 的视作不存在。
- 区间加，区间（全局亦可） kth。
同理，直接归约到区间删除，可撤销，区间 kth。
- link, cut, 区间 kth
用 link 和 cut 把删除的放一边，没删除的放另一边，当然这里的 kth 也能换成 \(\leq x\) 的个数。
- 区间 reverse，区间 kth
也是每次把删除了的块用 reverse 扔到一边。
再随便列几个：
- 区间覆盖，可撤销，全局 kth（归约到区间删除 可撤销）
- 交换一个前缀和一个后缀，区间 kth（link cut 归约到这个）
- 区间乘，区间 kth（和区间加一样归约）
- 区间复制，区间 kth