大家好，我非常喜欢暴力数据结构，于是我就用带修莫队套分块过了这道题
1. 前置芝士
带修莫队和分块。
2. 题解
发现这题只有一个单点修改，于是考虑带修莫队。
我们把普通莫队强行加上一个时间维 \(t\)，表示当前经过的修改次数，就变成带修莫队了。
带修莫队的过程如下：
将询问离线，对原序列以 \(n^\frac 2 3\) 的块长分块。对于区间 \([l, r, t]\)，按照 \(l\) 所在块为第一关键字，\(r\) 所在块为第二关键字，\(t\) 为第三关键字从小到大排序。
顺序处理每个询问，我们暴力从上一个区间转移到下一个区间，从上一个时间转移到下一个时间，这样的复杂度为 \(O(n^\frac 5 3)\)。
然后我们考虑如何维护答案，我们需要一个能支持如下操作这样的数据结构：
- 插入 \(x\) 数；
- 删除 \(x\) 数；
- 查询 \(x\) 数的排名；
- 查询排名为 \(x\) 的数；
- 求 \(x\) 的前驱；
- 求 \(x\) 的后继。
可以想到用平衡树，或者常数小的权值树状数组维护。这样修改和查询都是 \(O(\log n)\) 的，总复杂度 \(O(n^\frac 5 3 \log n)\)。
但其实可以用分块平衡复杂度，将修改的复杂度减少至 \(O(1)\)，查询复杂度增加至 \(O(\sqrt n)\)，总复杂度变为 \(O(n^\frac 5 3)\)。
具体的，首先对出现的数离散化到 \([1, n]\)，然后对值域分块，块内维护每个数出现的次数。
对于操作 1 2，单点修改即可。
void insert(int x) { ++val[x], ++sum[belong[x]]; }
void remove(int x) { --val[x], --sum[belong[x]]; }对于操作 3，直接对 \([1, x - 1]\) 区间求和即可。
int queryrank(int x) {
int res = 0;
for (int i = 1; i <= belong[x] - 1; i++) res += sum[i];
for (int i = x - 1; belong[i] == belong[x]; i--) res += val[i];
return res + 1;
}对于操作 4，从左到右扫一遍即可。
int querykth(int x) {
int i = 1, j = 1, cur = 0;
while (cur + sum[i] < x) cur += sum[i++], j += siz;
while (cur + val[j] < x) cur += val[j++];
return j;
}对于操作 5 6，可以转换为操作 2 3。
int querypre(int x) { return querykth(queryrank(x) - 1); }
int querynext(int x) { return querykth(queryrank(x + 1)); }3. Code
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
using namespace std;
const int N = 1e5 + 5;
int n, m, m1, m2, l = 1, r, t, a[N], b[N], belong[N], val[N], sum[N], siz, cnt;
struct node {
int op, l, r, x, k, t, id, ans;
} q[N], u[N];
bool cmp1(node a, node b) {
if (belong[a.l] != belong[b.l]) return a.l < b.l;
if (belong[a.r] != belong[b.r]) return a.r < b.r;
return a.t < b.t;
}
bool cmp2(node a, node b) { return a.id < b.id; }
void build1() {
siz = pow(n, 2.0 / 3.0);
for (int i = 1; i <= n; i++) belong[i] = (i - 1) / siz + 1;
}
void build2() {
siz = sqrt(cnt);
for (int i = 1; i <= cnt; i++) belong[i] = (i - 1) / siz + 1;
}
void insert(int x) { ++val[a[x]], ++sum[belong[a[x]]]; }
void remove(int x) { --val[a[x]], --sum[belong[a[x]]]; }
void update(int x) {
if (l <= u[x].x && u[x].x <= r) remove(u[x].x);
swap(a[u[x].x], u[x].k);
if (l <= u[x].x && u[x].x <= r) insert(u[x].x);
}
int queryrank(int x) {
int res = 0;
for (int i = 1; i <= belong[x] - 1; i++) res += sum[i];
for (int i = x - 1; belong[i] == belong[x]; i--) res += val[i];
return res + 1;
}
int querykth(int x) {
if (x < 1) return cnt + 1;
if (x > r - l + 1) return cnt + 2;
int i = 1, j = 1, k = 0;
while (k + sum[i] < x) k += sum[i++], j += siz;
while (k + val[j] < x) k += val[j++];
return j;
}
int querypre(int x) { return querykth(queryrank(x) - 1); }
int querynext(int x) { return querykth(queryrank(x + 1)); }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
cnt = n;
for (int i = 1; i <= n; i++) cin >> a[i], b[i] = a[i];
for (int i = 1, op, l, r, x, k; i <= m; i++) {
cin >> op;
if (op == 3) {
cin >> x >> k;
u[++m2] = {op, 0, 0, x, k, m2, m1};
} else {
cin >> l >> r >> k;
q[++m1] = {op, l, r, 0, k, m2, m1};
}
if (op != 2) b[++cnt] = k;
}
sort(b + 1, b + cnt + 1);
cnt = unique(b + 1, b + cnt + 1) - b - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
for (int i = 1; i <= m1; i++)
if (q[i].op != 2) q[i].k = lower_bound(b + 1, b + cnt + 1, q[i].k) - b;
for (int i = 1; i <= m2; i++)
if (u[i].op != 2) u[i].k = lower_bound(b + 1, b + cnt + 1, u[i].k) - b;
b[cnt + 1] = numeric_limits<int>::min() + 1;
b[cnt + 2] = numeric_limits<int>::max();
build1();
sort(q + 1, q + m1 + 1, cmp1);
build2();
for (int i = 1; i <= m1; i++) {
while (l > q[i].l) insert(--l);
while (r < q[i].r) insert(++r);
while (l < q[i].l) remove(l++);
while (r > q[i].r) remove(r--);
while (t < q[i].t) update(++t);
while (t > q[i].t) update(t--);
if (q[i].op == 1) q[i].ans = queryrank(q[i].k);
else if (q[i].op == 2) q[i].ans = b[querykth(q[i].k)];
else if (q[i].op == 4) q[i].ans = b[querypre(q[i].k)];
else if (q[i].op == 5) q[i].ans = b[querynext(q[i].k)];
}
sort(q + 1, q + m1 + 1, cmp2);
for (int i = 1; i <= m1; i++) cout << q[i].ans << '\n';
return 0;
}