Solution P4119
历经 纪念一下。
- 题意
给一个长度为
1 l r x y将区间[l,r] 中的x 改为y 。2 l r k查询区间第k 小。
- 分析
介绍一下，这种算法叫“望月悲叹的最初分块”，lxl 评分
首先考虑如何处理询问，有主席树等在线做法，当然也可以分块套值域树状数组（似乎分块套树状数组能做的值域分块都能做？），但这里使用值域分块。
我们希望将查询复杂度控制在
于是设
接下来，思考一下怎么修改。
对于边角块，直接暴力重构，复杂度
对于整块，分为以下三类：
- 不存在
x ，这种块直接忽略。 - 存在
x ，不存在y ，将x 映射到y 即可，具体来讲，我们见每个点拆成数x 对应的值，和值为x 对应的点两类。我们令val_x 表示数x 对应的真实值，pos_x 为值x 对应的点，修改时直接令val_{pos_x}=y ，同时保证再次修改时从y 更新到a_i ，将pos_y \leftarrow pos_x 。 - 即存在
x 又存在y ，由于每次合并不同数字的个数减1 ，所以这种合并最多经行n 次，那就暴力重构就好了。
时间复杂度
由于我的写法常数太大，只获得了
- 首先注意直接省略
x=y 的询问，不然会全 TLE。 - 边角块修改同样可以应用
x 不存在就省略的策略。 - 在初始化的时候，可以每次记录前面的值域，前缀和可以只从这个范围更新。
- 查询后清空数组太慢了，用一个栈存一下要清空哪些数可以快很多。
优化后期望得分
- code
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
using namespace std;
namespace IO{
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define reg register
inline long long read () {
reg char ch = gh();
reg long long x = 0;
reg char t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? -x : x;
}
inline void write(long long x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
}
using IO::read;
using IO::write;
const int maxn(1e5 + 50), maxk(325), sqv(316), lenv(317);
int n, T, sqn, len, a[maxn], id[maxn], ls[maxk], rs[maxk], b[maxk][maxk], c[maxk][maxn], cntx[maxk], cnty[maxk], cx[maxk], cy[maxk], tx[maxk], ty[maxn], idv[maxn], mx1, mx2;
int stk1[maxk << 1], top1, stk2[maxk << 1], top2;
struct Block {
int pos[maxn], val[maxn], now;
inline void build () {
for (int i = 1; i <= mx1; i++) b[now][i] = b[now - 1][i];
for (int i = 1; i <= mx2; i++) c[now][i] = c[now - 1][i];//继承值域的优化
for (int i = ls[now]; i <= rs[now]; i++) {
id[i] = now;
b[now][idv[a[i]]]++;
c[now][a[i]]++;
mx1 = max(mx1, idv[a[i]]);
mx2 = max(mx2, a[i]);
val[a[i]] = a[i];
pos[a[i]] = a[i];
}
}//初始化 b,c 和 pos,val
inline void rebuild (int x, int y) {
b[now][idv[x]] = b[now - 1][idv[x]];
b[now][idv[y]] = b[now - 1][idv[y]];
c[now][x] = c[now - 1][x];
c[now][y] = c[now - 1][y];//重构的过程中同样注意到只有 x，y 的值会发生改变，保证复杂度为 O(sqrt(n))
for (int i = ls[now]; i <= rs[now]; i++) {
if (a[i] == x) c[now][x]++;
else if (a[i] == y) c[now][y]++;
if (idv[a[i]] == idv[x]) b[now][idv[x]]++;
else if (idv[a[i]] == idv[y]) b[now][idv[y]]++;
val[a[i]] = a[i];
pos[a[i]] = a[i];
}
}
inline void mdy (int x, int y) {
val[pos[x]] = y;
pos[y] = pos[x];
pos[x] = 0;//将 x 映射到 y
}
inline int reduct (int x) {
return val[x];//x 的真实值
}
} G[maxk];
inline int qry (int k, int L, int R) {
int pos = 1;
while (k > (b[R][pos] - b[L - 1][pos] + tx[pos])) k -= (b[R][pos] - b[L - 1][pos] + tx[pos]), pos++;//先枚举在那个值域块
int i = (pos - 1) * sqv + 1;
while (k > (c[R][i] - c[L - 1][i] + ty[i])) k -= (c[R][i] - c[L - 1][i] + ty[i]), i++;//枚举是值域块中的那个数
return i;
}
int main () {
n = read(), T = read(), sqn = sqrt(n), len = (n - 1) / sqn + 1;
for (int i = 1; i <= len; ++i) ls[i] = rs[i - 1] + 1, rs[i] = i * sqn; rs[len] = n;
for (int i = 1; i <= 100000; ++i) idv[i] = (i - 1) / sqv + 1;
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= len; ++i) G[i].now = i, G[i].build();
while (T--) {
int opt = read(), l = read(), r = read();
if (opt == 1) {
int x = read(), y = read(), ll = id[l], rr = id[r];
if (x == y) continue;//这里没写 0pts，调了一天……
for (int i = ll + 1; i <= len; ++i) cntx[i] = c[i][x] - c[i - 1][x], cnty[i] = c[i][y] - c[i - 1][y], cx[i] = b[i][idv[x]] - b[i - 1][idv[x]], cy[i] = b[i][idv[y]] - b[i - 1][idv[y]];
//cntx[i] 表示第 i 块中 x 的个数，cnty[i] 同理，cx[i] 表示第 i 块中 x 所在值域块的数的个数
if (ll == rr) {
if (c[ll][x] == c[ll - 1][x]) continue;
for (int i = ls[ll]; i <= rs[ll]; ++i) a[i] = G[ll].reduct(a[i]);
for (int i = l; i <= r; ++i) if (a[i] == x) a[i] = y;
G[ll].rebuild(x, y);
for (int i = ll + 1; i <= len; ++i) {
b[i][idv[x]] = b[i - 1][idv[x]] + cx[i];
b[i][idv[y]] = b[i - 1][idv[y]] + cy[i];
c[i][x] = c[i - 1][x] + cntx[i];
c[i][y] = c[i - 1][y] + cnty[i];
}
continue;
}
if (c[ll][x] != c[ll - 1][x]) {//优化边角重构
for (int i = ls[ll]; i <= rs[ll]; ++i) a[i] = G[ll].reduct(a[i]);
for (int i = l; id[i] == ll; ++i) if (a[i] == x) a[i] = y;
G[ll].rebuild(x, y);
}
for (int i = ll + 1; i <= len; i++) {
if (i > rr || !cntx[i]) {//忽略不存在 x 的块
b[i][idv[x]] = b[i - 1][idv[x]] + cx[i];
b[i][idv[y]] = b[i - 1][idv[y]] + cy[i];
c[i][x] = c[i - 1][x] + cntx[i];
c[i][y] = c[i - 1][y] + cnty[i];
continue;
}
if (i == rr) {
for (int j = ls[rr]; j <= rs[rr]; ++j) a[j] = G[rr].reduct(a[j]);
for (int j = r; id[j] == rr; --j) if (a[j] == x) a[j] = y;
G[rr].rebuild(x, y);
continue;
}
if (cnty[i]) {
for (int j = ls[i]; j <= rs[i]; ++j) a[j] = G[i].reduct(a[j]);
for (int j = ls[i]; j <= rs[i]; ++j) if (a[j] == x) a[j] = y;
G[i].rebuild(x, y);
} else {
G[i].mdy(x, y);
if (idv[x] != idv[y]) b[i][idv[x]] = b[i - 1][idv[x]] + cx[i] - cntx[i], b[i][idv[y]] = b[i - 1][idv[y]] + cy[i] + cntx[i];
else b[i][idv[x]] = b[i - 1][idv[x]] + cx[i];
c[i][x] = c[i - 1][x];
c[i][y] = c[i - 1][y] + cntx[i];
}
}
} else {
int k = read(), ll = id[l], rr = id[r];
if (ll == rr) {
for (int i = l; i <= r; ++i) {
int v = G[ll].reduct(a[i]);
if (!tx[idv[v]]) stk1[++top1] = idv[v];
tx[idv[v]]++;
if (!ty[v]) stk2[++top2] = v;
ty[v]++;
}
write(qry(k, 1, 0)), puts("");
while (top1) tx[stk1[top1--]] = 0;
while (top2) ty[stk2[top2--]] = 0;
continue;
}
for (int i = l; id[i] == ll; ++i) {
int v = G[ll].reduct(a[i]);
if (!tx[idv[v]]) stk1[++top1] = idv[v];
tx[idv[v]]++;
if (!ty[v]) stk2[++top2] = v;
ty[v]++;
}
for (int i = r; id[i] == rr; --i) {
int v = G[rr].reduct(a[i]);
if (!tx[idv[v]]) stk1[++top1] = idv[v];
tx[idv[v]]++;
if (!ty[v]) stk2[++top2] = v;
ty[v]++;
}
write(qry(k, ll + 1, rr - 1)), puts("");
while (top1) tx[stk1[top1--]] = 0;
while (top2) ty[stk2[top2--]] = 0;//用栈优化清空的过程
}
}
}