首切 Ynoi QAQ 调了4个小时
题目描述
写个支持以下操作的数据结构：
对于长度为 \(n\) 的序列 \(a\)，
-
给定 \(l,r,k\), 求序列 \(a\) 在该区间的 kth
-
给定 \(l,r,x,y\), \(a_i \gets y ~(l\leq i\leq r,a_i=x)\)
\(n,m,a_i,x,y\leq 10^5\), \(m\)为操作数
题目分析
由于是Ynoi，所以分块呃呃呃 /kel
由于替换操作的存在，用树套树维护不太行（应该是不低于3log的），考虑分块。
如果是静态区间kth，怎么拿分块做呢？
单单序列分块做不了，可以参照可持久化权值线段树维护值域的思想，给值域也分块，就有了下面的静态做法：
开两个数组 \(g_{i,j}\) 和 \(cnt_{i,j}\)，其中 \(g_{i,j}\) 记录序列的 前 \(i\) 个块中数值在值域里 第 \(j\) 个块的数的数量，\(cnt_{i,j}\) 表示序列的前 \(i\) 的块中数值 \(j\) 出现的次数。
于是对于每次询问，处理一下散块里的数，然后遍历一遍值域块就可以了。 时间复杂度 \(\mathcal{O}((n+m)\sqrt{n})\)。
接着考虑加上修改操作如何做。
我们的目标就是维护 \(cnt\) 和 \(g\) 数组，散块的似乎并不难处理，但是整块似乎不好处理，因为难以直接维护每个位置的值。
考虑一下操作2的性质，被操作的数在操作前后都是相等的，操作后又并入原来的 \(y\) 中（假设存在）。我们可以考虑用并查集来维护整块内每种相等的数的值。
具体地说，\(par_i\) 表示序列中第 \(i\) 个数在并查集里的祖先，如果序列中第 \(i\) 个数是它在的集合的根（即 \(par_i=i\)），用 \(num_i\) 记录它代表的值，同时用 \(wh_{i,j}\) 记录第 \(i\) 个块内代表值为 \(j\) 的集合的根所处的位置，不存在则为 0 。对于整块操作，维护这些并查集即可。散块暴力同理，但是需要注意区分一个数要不要被替换（具体细节在代码中）。
如果认为并查集时间复杂度均摊下来是 \(\mathcal{O}(1)\) 的话，算法的时间复杂度就是 \(\mathcal{O}((n+m)\sqrt{n})\)，理论上可以通过本题。
但是大概率要卡卡常，一些技巧塞到代码注释里了。