```
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e6 + 10, INF = 2e9;
int idx, w[N], n, m;
#define IN stdin->_IO_read_ptr<stdin->_IO_read_end?*stdin->_IO_read_ptr++:__uflow(stdin)
#define OUT(_ch) stdout->_IO_write_ptr<stdout->_IO_write_end?*stdout->_IO_write_ptr++=_ch:__overflow(stdout,_ch)
inline void read(int &x){
x=0;
char ch=IN;
while(ch<47)ch=IN;
while(ch>47)x=(x<<1)+(x<<3)+(ch^48),ch=IN;
}
inline void write(int x)
{
static char buf[16];
static int len=-1;
if(x<0)putchar('-'),x=-x;
do buf[++len]=x%10,x/=10;while(x);
while(len>=0)putchar(buf[len--]+'0');
putchar('\n');
}
struct Splay {
int s[2], p, v, size;
void init(int _p, int _v) {
p = _p, v = _v, size = 1;
}
};
struct Mathods_Splay {
Splay tr[N];
inline void pushup(int x) {
tr[x].size = tr[tr[x].s[0]].size + tr[tr[x].s[1]].size + 1;
}
inline void rotate(int x) {
int y = tr[x].p, z = tr[y].p, k = tr[y].s[1] == x;
if (z) tr[z].s[tr[z].s[1] == y] = x; tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}
inline void splay(int &root, int x, int k) {
while (tr[x].p != k) {
int y = tr[x].p, z = tr[y].p;
if (z != k) rotate(((tr[z].s[1] == y) ^ (tr[y].s[1] == x)) ? y : x);
rotate(x);
}
if (!k) root = x;
}
inline int find(int &root, int v) {
int u = root;
if (!u) return -1;
while (v != tr[u].v && tr[u].s[v > tr[u].v])
u = tr[u].s[v > tr[u].v];
splay(root, u, 0);
return u;
}
inline void insert(int &root, int v) {
int u = root, fa = 0;
while (u) fa = u, u = tr[u].s[v > tr[u].v];
u = ++ idx;
if (fa) tr[fa].s[v > tr[fa].v] = u;
tr[u].init(fa, v);
splay(root, u, 0);
}
inline int get_rank(int &root, int v) {
int u = root, res = 0;
while (u) {
if (tr[u].v < v) res += tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
else u = tr[u].s[0];
}
// splay(root, u, 0);
return res;
}
inline void update(int &root, int x, int y) {
int u = root;
while (u) {
if (tr[u].v == x) break;
if (tr[u].v < x) u = tr[u].s[1];
else u = tr[u].s[0];
}
splay(root, u, 0);
int l = tr[u].s[0], r = tr[u].s[1];
while (tr[l].s[1]) l = tr[l].s[1];
while (tr[r].s[0]) r = tr[r].s[0];
splay(root, l, 0), splay(root, r, l);
tr[r].s[0] = 0;
pushup(r), pushup(l);
insert(root, y);
}
inline int get_pre(int &root, int v) {
int u = root, res = -2147483647;
while (u) {
if (tr[u].v < v) res = max(res, tr[u].v), u = tr[u].s[1];
else u = tr[u].s[0];
}
// splay(root, u, 0);
return res;
}
inline int get_next(int &root, int v) {
int u = root, res = 2147483647;
while (u) {
if (tr[u].v > v) res = min(res, tr[u].v), u = tr[u].s[0];
else u = tr[u].s[1];
}
// splay(root, u, 0);
return res;
}
}s;
struct Tree {
int l, r;
int root;
}tr[N << 2];
inline void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
s.insert(tr[u].root, -INF), s.insert(tr[u].root, INF);
for (register int i = l; i <= r; i ++ )
s.insert(tr[u].root, w[i]);
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
inline int query_rank(int u, int l, int r, int v) {
if (tr[u].l >= l && tr[u].r <= r) return s.get_rank(tr[u].root, v) - 1;
int mid = tr[u].l + tr[u].r >> 1, res = 0;
if (l <= mid) res += query_rank(u << 1, l, r, v);
if (r > mid) res += query_rank(u << 1 | 1, l, r, v);
return res;
}
inline void modify(int u, int x, int v) {
s.update(tr[u].root, w[x], v);
if (tr[u].l == tr[u].r) return;
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
}
inline int query_pre(int u, int l, int r, int x) {
if (tr[u].l >= l && tr[u].r <= r) return s.get_pre(tr[u].root, x);
int mid = tr[u].l + tr[u].r >> 1, res = -2147483647;
if (l <= mid) res = max(res, query_pre(u << 1, l, r, x));
if (r > mid) res = max(res, query_pre(u << 1 | 1, l, r, x));
return res;
}
inline int query_next(int u, int l, int r, int x) {
if (tr[u].l >= l && tr[u].r <= r) return s.get_next(tr[u].root, x);
int mid = tr[u].l + tr[u].r >> 1, res = 2147483647;
if (l <= mid) res = min(res, query_next(u << 1, l, r, x));
if (r > mid) res = min(res, query_next(u << 1 | 1, l, r, x));
return res;
}
int main()
{
read(n), read(m);
int minn = INF, maxn = -INF;
for (register int i = 1; i <= n; i ++ ) {
read(w[i]);
minn = min(minn, w[i]), maxn = max(maxn, w[i]);
}
build(1, 1, n);
int op, l, r, k;
while (m -- ) {
read(op), read(l), read(r);
if (op == 1) {
read(k);
printf("%d\n", query_rank(1, l, r, k) + 1);
}
if (op == 2) {
read(k);
int L = minn, R = maxn;
while (L < R) {
int mid = L + R + 1 >> 1;
if (query_rank(1, l, r, mid) + 1 <= k) L = mid;
else R = mid - 1;
}
printf("%d\n", R);
}
if (op == 3) {
minn = min(minn, r), maxn = max(maxn, r);
modify(1, l, r);
w[l] = r;
}
if (op == 4) {
read(k);
printf("%d\n", query_pre(1, l, r, k) == -INF ? -2147483647 : query_pre(1, l, r, k));
}
if (op == 5) {
read(k);
printf("%d\n", query_next(1, l, r, k) == INF ? 2147483647 : query_next(1, l, r, k));
}
}
return 0;
}
```
by Link_Cut_Y @ 2022-07-29 19:24:54
你快读没负数？
by 黑影洞人 @ 2022-07-29 19:31:01
@[黑影洞人](/user/285617) 本题没负数啊。
by Usada_Pekora @ 2022-07-29 19:50:06
@[黑影洞人](/user/285617) 知道错哪了，主要是因为权值平衡树插点的时候，应该记一个 $\texttt{cnt}$ 表示出现该权值的次数，这样能够有效减少 $\texttt{splay}$ 中点的数量，从而降低复杂度。
by Link_Cut_Y @ 2022-07-29 22:19:39
@[Mount_](/user/519384) 这毛病我之前犯过
by 黑影洞人 @ 2022-07-29 22:22:10
@[黑影洞人](/user/285617) hh，看来还是我太弱了
by Link_Cut_Y @ 2022-07-29 22:24:16
@[Mount_](/user/519384) 我树套树一直0分，没调出来，干脆放弃去学fhq-treap了，你比我强耶
by 黑影洞人 @ 2022-07-29 22:27:46