@[AAA404](/user/723198)
这样不是更简单吗
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 114514;
int n, m, top, cnt1, cnt2, cnt3, a[N];
int root[N], tmp1[N], tmp2[N], lsh[N << 1];
int opt[N], l[N], r[N], k[N];
struct { int v, l, r; } tr[N << 7];
constexpr int lowbit(int x) {
return x & -x;
}
void pushup(int u) {
tr[u].v = tr[tr[u].l].v + tr[tr[u].r].v;
}
void change(int &u, int l, int r, int x, int v) {
if (!u) u = ++cnt1;
if (l == r) tr[u].v += v;
else {
int mid = l + r >> 1;
if (x <= mid) change(tr[u].l, l, mid, x, v);
else change(tr[u].r, mid + 1, r, x, v);
pushup(u);
}
}
void add(int u, int x) {
for (int i = u; i <= n; i += lowbit(i))
change(root[i], 1, top, a[u], x);
}
int query(int l, int r, int x) {
if (l == r) return l;
int cnt = 0, mid = l + r >> 1;
for (int i = 1; i <= cnt2; i++)
cnt += tr[tr[tmp1[i]].l].v;
for (int i = 1; i <= cnt3; i++)
cnt -= tr[tr[tmp2[i]].l].v;
if (x <= cnt) {
for (int i = 1; i <= cnt2; i++)
tmp1[i] = tr[tmp1[i]].l;
for (int i = 1; i <= cnt3; i++)
tmp2[i] = tr[tmp2[i]].l;
return query(l, mid, x);
} else {
for (int i = 1; i <= cnt2; i++)
tmp1[i] = tr[tmp1[i]].r;
for (int i = 1; i <= cnt3; i++)
tmp2[i] = tr[tmp2[i]].r;
return query(mid + 1, r, x - cnt);
}
}
int ask(int l, int r, int x) {
cnt2 = cnt3 = 0;
for (int i = r; i; i -= lowbit(i))
tmp1[++cnt2] = root[i];
for (int i = l - 1; i; i -= lowbit(i))
tmp2[++cnt3] = root[i];
return query(1, top, x);
}
int query2(int l, int r, int x) {
if (l == r) return 0;
int cnt = 0, mid = l + r >> 1;
if (x <= mid) {
for (int i = 1; i <= cnt2; i++)
tmp1[i] = tr[tmp1[i]].l;
for (int i = 1; i <= cnt3; i++)
tmp2[i] = tr[tmp2[i]].l;
return query2(l, mid, x);
} else {
for (int i = 1; i <= cnt2; i++)
cnt += tr[tr[tmp1[i]].l].v;
for (int i = 1; i <= cnt3; i++)
cnt -= tr[tr[tmp2[i]].l].v;
for (int i = 1; i <= cnt2; i++)
tmp1[i] = tr[tmp1[i]].r;
for (int i = 1; i <= cnt3; i++)
tmp2[i] = tr[tmp2[i]].r;
return cnt + query2(mid + 1, r, x);
}
}
int ask2(int l, int r, int x) {
cnt2 = cnt3 = 0;
for (int i = r; i; i -= lowbit(i))
tmp1[++cnt2] = root[i];
for (int i = l - 1; i; i -= lowbit(i))
tmp2[++cnt3] = root[i];
return query2(1, top, x) + 1;
}
int askpre(int l, int r, int x) {
int rnk = ask2(l, r, x) - 1;
return rnk ? ask(l, r, rnk) : 0;
}
int asknxt(int l, int r, int x) {
if (top == x) return top + 1;
int rnk = ask2(l, r, x + 1);
return rnk == r - l + 2 ? top + 1 : ask(l, r, rnk);
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i], lsh[++top] = a[i];
for (int i = 1; i <= m; i++) {
cin >> opt[i] >> l[i] >> r[i];
if (opt[i] != 3) cin >> k[i];
else lsh[++top] = r[i];
if (opt[i] == 4 || opt[i] == 5) lsh[++top] = k[i];
}
sort(lsh + 1, lsh + top + 1);
top = unique(lsh + 1, lsh + top + 1) - (lsh + 1);
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(lsh + 1, lsh + top + 1, a[i]) - lsh;
add(i, 1);
}
lsh[0] = -(lsh[top + 1] = INT_MAX);
for (int i = 1; i <= m; i++)
switch (opt[i]) {
case 1:
cout << ask2(l[i], r[i], lower_bound(lsh + 1, lsh + top + 1, k[i]) - lsh) << '\n';
break;
case 2:
cout << lsh[ask(l[i], r[i], k[i])] << '\n';
break;
case 3:
add(l[i], -1);
a[l[i]] = lower_bound(lsh + 1, lsh + top + 1, r[i]) - lsh;
add(l[i], 1);
break;
case 4:
cout << lsh[askpre(l[i], r[i], lower_bound(lsh + 1, lsh + top + 1, k[i]) - lsh)] << '\n';
break;
case 5:
cout << lsh[asknxt(l[i], r[i], lower_bound(lsh + 1, lsh + top + 1, k[i]) - lsh)] << '\n';
break;
}
}
```
也很短啊
by Carroty_cat @ 2023-08-27 17:47:26
@[Carroty_cat](/user/912750) 主要是想练线段树套平衡树
by AAA404 @ 2023-08-27 18:13:18
%%%
by qwef_ @ 2023-08-27 18:33:58