不明白为什么还有神笔在中考前一周故意恶心我啊。
在搞心态和文化课之间，我选择 OI。
$$\large\textbf{整体二分}$$
MET-Meteors \(\mathtt{[C|5.0]}\)
长度为 \(n\) 的环，每个节点有一个标签 \(c_i\)，初值为 \(0\)，\(m\) 次区间加操作，对于每个 \(c_i\)，求所有标签为 \(c_i\) 的节点在哪一次操作后值之和大于等于 \(k_{c_i}\)。
整体二分板题。
每个标签可以看成单个的询问。
对每个节点暴力二分答案的话，\(O(nk\log k)\)，T 飞了。
考虑将部分询问操作放在一个整体然后二分。
我们令 td(l,r,L,R) 表示对于数组位置在 \([L,R]\) 中的所有询问操作 \(t\)，答案在 \([l,r]\) 中。
二分答案 \([l,r]\)，每次取出一个中间值 \(mid\)。
用支持区间加的数据结构暴力处理 \([L,R]\) 中的区间加操作从上一次的位置到 \(mid\) 的状态，一并查询 \(L\le t\le R\) 的所有询问 \(t\)。
查询完后，将所有达到 \(k_t\) 的 \(t\) 和所有未达到 \(k_t\) 的 \(t\) 分成两组，前者中的所有 \(t\) 的答案一定在 \([l,mid]\) 中，后者中的答案一定在 \([mid+1,r]\) 中。
递归查询即可。
[View Code]
Dynamic Rankings \(\mathtt{[C|5.3]}\)
带修区间第 \(k\) 小。
区间第 \(k\) 小相当于区间中有 \(k-1\) 个数比它小。
我们令 td(l,r,L,R) 表示对于数组位置在 \([L,R]\) 中的所有询问操作 \(t\)，要查询的第 \(k\) 小值在 \([l,r]\) 中。
如何判断某个查询操作已经满足要求？执行 \([L,R]\) 中所有值小于 \(mid\) 的单点修改操作，将该点的值修改为 \(1\)。查询区间中所有点的值的和，判断是否小于 \(k-1\) 即可。
[View Code]
矩阵乘法 \(\mathtt{[C|5.5]}\)
给你一个 \(n\times n\) 的矩阵，不用算矩阵乘法，但是每次询问一个子矩阵的第 \(k\) 小数。
矩阵可以看成 \(n^2\) 个单点修改操作。
同上题，只不过树状数组从一维的变成了二维的。