题解：P12485 [集训队互测 2024] PM 大师

击杀了这个题很爽，想到了转置就全对了！

用 $a_i=0$ 给所有位置分段，相当于每段有一个集合 $S_i$。从值域的角度入手，处理出元素 $v$ 的极长未出现前缀长度 $c$，所有 $a_i=0$ 位置的 $b_q$ 的生成方式形如：维护当前值 $p$ 以及位置 $q$，找到 $>p$ 中最小的 $c_{p'}>q$，然后 $p\to p',q\to q+1$。一个位置修改时，会影响后面点的排名，但是被选入答案的点的集合变化量是 $\mathcal O(1)$ 的。维护被选入 $p$ 的所有值构成的集合 $T$，尝试找到 $T$ 的变化。

想到这个之后前 $4$ 个 sub 都是平凡的。

subtask5：只向某个集合插入元素。考虑在集合 $x$ 插入 $k$ 的影响，不妨设此时令 $c_k\to x-1$。若 $k$ 存在于 $T$ 且在 $T$ 的排名 $\ge x$ 那么需要向 $k$ 后面找到一个插入 $T$ 的元素。用一点数据结构手法，对于值 $v$ 维护 $f_v=\sum_{i\in T}[i<v]-c_v$（显然除去 $c_v=m+1$ 的 $c$ 是互不相同的）。对于 $v\in T$，发现其等价于 $f_v<0$，$f_v\ge 0$ 等价于 $v\not\in T$。对 $f$ 做区间加/减，找到 $f_i=0$ 的位置调整到 $T$ 里即可。

拓展到从集合中删除元素：可能将修改的 $k$ 加入 $T$ 中，反过来维护一个 $g_v$。使用线段树支持对 $f,g$ 的区间加以及最小值位置的提取。时间复杂度 $\mathcal O(n\log n)$。