题目大意:
给了你一个长为n的序列a，有m次操作
1.把区间[l,r]内所有x变成y
2.查询区间[l,r]内k小值
即:区间所有x变y,区间第k小.
对于区间第k小问题,我们进行权值分块,记b[i][j]为前i个位置块内,权值在第j权值块以下的数字个数,cnt[i][j]表示前i个块内数字x的出现次数.
查询时,先把散块信息处理出来.此时我们可以O(1)得到询问区间内权值在第j权值块以下的数字个数以及询问区间内每个数的出现个数.查询时暴力遍历每个权值块,找到第一个数字个数>k的权值块,则第k大必定在此块内.在块内暴力查找第k小,查询复杂度为O(msqrt(n)).
对于修改操作.考虑将整块中的x全部变成y时,则块内数字种类数要么不变要么-1.当块内不存在y时,直接随意搞一个映射将块内的x映射成y并且更新信息.当块内x与y都存在时直接重构整个块.重构复杂度O(sqrt(n)),最多有n+m种权值,因此修改复杂度为O((n+m)sqrt(n)).
注意特判x=y时不进行修改,不然可能爆复杂度.
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100100, MAXB = 320, M = 100050;
void read(int &x) {char ch;while(ch=getchar(),ch<'!');x=ch-48;while(ch=getchar(),ch>'!')x=(x<<3)+(x<<1)+ch-48;}
int n, m, L[MAXN], R[MAXN], Psiz, b[MAXB][1050], fh[MAXB][1050], h[MAXB][MAXN], ls[MAXN], ls2[2050], c[MAXN], a[MAXN], Vsiz, cnt[MAXB][MAXN], Q, _m;
void rep(int p) {for(int i = L[p]; i < R[p]; ++i) a[i] = fh[p][c[i]];}
void change(int B, int x, int y) {int id = h[B][x]; h[B][y] = id; fh[B][id] = y; h[B][x] = 0;}
inline int Vbl(int x) {return x/Vsiz;} inline int Pbl(int x) {return x/Psiz;}
void Rebuild(int p, int op = 1) {
if(op) for(int i = 1; i <= Psiz; ++i) h[p][fh[p][i]] = 0;
for(int top = 0, i = L[p]; i < R[p]; ++i) if(!h[p][a[i]]) h[p][a[i]] = ++top, fh[p][top] = a[i];
for(int i = L[p]; i < R[p]; ++i) c[i] = h[p][a[i]];
}
int main() {
read(n); read(Q); Psiz = Vsiz = 600; m = n/Psiz+1; _m = M/Vsiz+1;
for(int i = 0; i < n; ++i) read(a[i]);
for(int i = 0; i < m+10; ++i) L[i] = i*Psiz, R[i] = min((i+1)*Psiz, n);
for(int i = 0; i < m; ++i) Rebuild(i, 0);
for(int i = 0; i < m; ++i) {
if(i) {
for(int j = 0; j < M; ++j) cnt[i][j] = cnt[i-1][j];
for(int j = 0; j < _m; ++j) b[i][j] = b[i-1][j];
}
for(int j = L[i]; j < R[i]; ++j) ++cnt[i][a[j]], ++b[i][Vbl(a[j])];
}
for(int op, l, r, x, y; Q--; ) {
read(op); read(l); read(r); --l; --r;
if(op == 1) {
read(x); read(y); if(x == y) continue;
int bl = Pbl(l), br = Pbl(r), bx = Vbl(x), by = Vbl(y);
if(cnt[br][x] - (bl?cnt[bl-1][x]:0) == 0) continue;
for(int i = m-1; i >= 1 && i >= bl; --i) {
cnt[i][x] -= cnt[i-1][x]; cnt[i][y] -= cnt[i-1][y];
b[i][bx] -= b[i-1][bx]; b[i][by] -= b[i-1][by];
}
if(bl == br) {
rep(bl);
for(int i = l; i <= r; ++i)
if(a[i] == x) {
a[i] = y;
--cnt[bl][x]; ++cnt[bl][y];
--b[bl][bx]; ++b[bl][by];
}
Rebuild(bl);
} else {
rep(bl); rep(br);
for(int i = l; i < R[bl]; ++i)
if(a[i] == x) {
a[i] = y;
--cnt[bl][x]; ++cnt[bl][y];
--b[bl][bx]; ++b[bl][by];
}
for(int i = L[br]; i <= r; ++i)
if(a[i] == x) {
a[i] = y;
--cnt[br][x]; ++cnt[br][y];
--b[br][bx]; ++b[br][by];
}
Rebuild(bl); Rebuild(br);
for(int i = bl+1; i < br; ++i)
if(cnt[i][x]) {
if(cnt[i][y]) {
rep(i);
for(int j = L[i]; j < R[i]; ++j)
if(a[j] == x) {
a[j] = y;
--cnt[i][x]; ++cnt[i][y];
--b[i][bx]; ++b[i][by];
}
Rebuild(i);
} else {
b[i][by] += cnt[i][x]; b[i][bx] -= cnt[i][x];
cnt[i][y] += cnt[i][x]; cnt[i][x] = 0;
change(i, x, y);
}
}
}
for(int i = max(1, bl); i < m; ++i) {
cnt[i][x] += cnt[i-1][x]; cnt[i][y] += cnt[i-1][y];
b[i][bx] += b[i-1][bx]; b[i][by] += b[i-1][by];
}
}
else {
read(x); int bl = Pbl(l), br = Pbl(r);
if(bl == br) {
rep(bl);
for(int i = l; i <= r; ++i) ls[i] = a[i];
nth_element(ls+l, ls+l+x-1, ls+r+1);
printf("%d\n", ls[l+x-1]);
for(int i = l; i <= r; ++i) ls[i] = 0;
} else {
rep(bl); rep(br);
for(int i = l; i < R[bl]; ++i) ++ls[a[i]], ++ls2[Vbl(a[i])];
for(int i = L[br]; i <= r; ++i) ++ls[a[i]], ++ls2[Vbl(a[i])];
for(int i = 0, sum = 0; i < _m; ++i) {
if(ls2[i] + b[br-1][i] - b[bl][i] + sum >= x) {
int flag = 0;
for(int j = i*Vsiz; j < (i+1)*Vsiz; ++j) {
if(ls[j] + cnt[br-1][j] - cnt[bl][j] + sum >= x) {
printf("%d\n", j); flag = 1; break;
} else sum += ls[j] + cnt[br-1][j] - cnt[bl][j];
}
if(flag) break;
} else sum += ls2[i] + b[br-1][i] - b[bl][i];
}
for(int i = l; i < R[bl]; ++i) --ls[a[i]], --ls2[Vbl(a[i])];
for(int i = L[br]; i <= r; ++i) --ls[a[i]], --ls2[Vbl(a[i])];
}
}
}
}
