\(\text{Links}\)
题外话
-
个人生涯中第一道独立通过的 Ynoi 大分块！！
-
同时也是个人生涯中通过的第十道 Ynoi 系列题目！！
-
卡了好久结果加了个优化就过了/yun
-
AC 那一瞬间的场面好像 56 Seconds Later/ll
-
感觉 \(8.5\) 的评分还是有点虚高（，个人体感 \(7\)。
题意
-
将区间内的所有 \(x\) 变成 \(y\)
-
查询区间第 \(k\) 小
\(1\le n,m,a_i\le 10^5\)
题解
首先考虑静态区间第 \(k\) 小怎么做。
可以二分答案，然后查询区间内 \(\le x\) 的数量，\(O(n\sqrt n\log n)\)。
套个值域分块，分别记录序列上前 \(i\) 个块中 \(j\) 的出现次数和第 \(j\) 个值域块中的值的出现次数之和。查询时先把散块的信息处理出来，再扫值域块 \(O(1)\) 累加次数，确定答案在哪个值域块，然后进入答案块中继续 \(O(1)\) 累加次数，直到加到 \(\ge k\) 就找到了答案。
然后考虑修改，维护上面提到的那些信息都很简单，把之前的 \(cnt_x\) 求出来，然后往后暴力更新就好了。
但是散块的查询就会比较难整，那么考虑怎样查询每个位置的值。
结合上修改操作，再加上第二分块赋予的经验，不难想到用并查集维护，在每个块内把相同颜色的位置并在一起，修改的时候整块直接把 \(x\) 并给 \(y\)，散块暴力重构就好了。查询散块的时候直接 \(\text{find}\) 每个位置的值就好。
\(O(n\alpha(n)\sqrt n)\)。
进入正题 卡常
-
块长稍微开大一点吧，大概不低于 \(300\)，本人 AC 的时候取的是 \(400\)。
-
修改操作暴力重构散块的时候，忽略除了 \(x\) 和 \(y\) 以外的值！本人就是靠这个优化 AC 的！
-
同块内的查询直接 \(\text{nth-element}\)。
-
\(\text{fread + cout}\)