题目大意：有$5$种操作：
- $1\;l\;r\;k：$查询$k$在区间$[l,r]$内的排名
- $2\;l\;r\;k：$查询区间$[l,r]$内排名为$k$的值
- $3\;pos\;k：$把第$pos$为上的数值改为$k$
- $4\;l\;r\;k：$查询$k$在区间$[l,r]$内的前驱
- $5\;l\;r\;k：$查询$k$在区间$[l,r]$内的后继
题解：树套树，权值线段树套平衡树
卡点：$TLE$卡了一会（我好菜啊）
C++ Code：
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cctype> //#define ONLINE_JUDGE
namespace __IO {
namespace R {
int x;
#ifdef ONLINE_JUDGE
#define M (1 << 24)
char op[M], *ch = op;
inline void begin() {
fread(op, 1, M, stdin);
}
inline int read() {
while (isspace(*ch)) ch++;
for (x = *ch & 15, ch++; isdigit(*ch); ch++) x = x * 10 + (*ch & 15);
return x;
}
#undef M
#else
int ch;
inline int read() {
ch = getchar();
while (isspace(ch)) ch = getchar();
for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
return x;
}
#endif
} namespace W {
#ifdef ONLINE_JUDGE
#define M (1 << 24)
char op[M], *ch = op - 1;
inline void end() {
fwrite(op, 1, ch - op + 1, stdout);
}
inline void write(int x) {
if (x > 9) write(x / 10);
*++ch = x % 10 ^ 48;
}
#undef M
#else
inline void write(int x) {
if (x > 9) write(x / 10);
putchar(x % 10 ^ 48);
}
#endif
}
}
using __IO::R::read;
using __IO::W::write; #define maxn 50010
#define N (maxn * 50)
const int inf = 0x7fffffff, maxl = 0, maxr = 1e8; namespace Treap {
int lc[N], rc[N], V[N], pri[N], sz[N];
int res, idx, ta, tb, tmp; inline int nw(int x) {
V[++idx] = x, sz[idx] = 1, pri[idx] = rand();
return idx;
}
inline int update(int rt) {
sz[rt] = sz[lc[rt]] + sz[rc[rt]] + 1;
return rt;
} void split(int rt, int k, int &x, int &y) {
if (!rt) x = y = 0;
else {
if (V[rt] <= k) split(rc[rt], k, rc[rt], y), x = update(rt);
else split(lc[rt], k, x, lc[rt]), y = update(rt);
}
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (pri[x] < pri[y]) {rc[x] = merge(rc[x], y); return update(x);}
else {lc[y] = merge(x, lc[y]); return update(y);}
} void insert(int &rt, int x) {
if (!rt) rt = nw(x);
else {
split(rt, x, ta, tb);
rt = merge(ta, merge(nw(x), tb));
}
}
void erase(int &rt, int x) {
split(rt, x, ta, tb);
split(ta, x - 1, ta, tmp);
rt = merge(ta, tb);
}
int gtrnk(int &rt, int l, int r) {
split(rt, l - 1, ta, tb);
split(tb, r, tmp, tb);
res = sz[tmp];
rt = merge(ta, merge(tmp, tb));
return res;
}
} namespace SgT {
int lc[N], rc[N], rt[N], idx;
int root; int pos, num;
void __insert(int &rt, int l, int r) {
if (!rt) rt = ++idx;
Treap::insert(SgT::rt[rt], pos);
if (l == r) return ;
int mid = l + r >> 1;
if (num <= mid) __insert(lc[rt], l, mid);
else __insert(rc[rt], mid + 1, r);
}
void insert(int __pos, int __num) {
pos = __pos, num = __num;
__insert(root, maxl, maxr);
} void __erase(int rt, int l, int r) {
Treap::erase(SgT::rt[rt], pos);
if (l == r) return ;
int mid = l + r >> 1;
if (num <= mid) __erase(lc[rt], l, mid);
else __erase(rc[rt], mid + 1, r);
}
void erase(int __pos, int __num) {
pos = __pos, num = __num;
__erase(root, maxl, maxr);
} int L, R, val;
int __gtrnk(int rt, int l, int r) {
if (l == r) return 1;
int mid = l + r >> 1;
if (val <= mid) return __gtrnk(lc[rt], l, mid);
else return Treap::gtrnk(SgT::rt[lc[rt]], L, R) + __gtrnk(rc[rt], mid + 1, r);
}
int gtrnk(int __L, int __R, int __val) {
L = __L, R = __R, val = __val;
return __gtrnk(root, maxl, maxr);
} int __gtkth(int rt, int l, int r, int k) {
if (l == r) return l;
int mid = l + r >> 1, tmp = Treap::gtrnk(SgT::rt[lc[rt]], L, R);
if (tmp >= k) return __gtkth(lc[rt], l, mid, k);
else return __gtkth(rc[rt], mid + 1, r, k - tmp);
}
int gtkth(int __L, int __R, int k) {
L = __L, R = __R;
return __gtkth(root, maxl, maxr, k);
} int pre(int L, int R, int x) {
int k = gtrnk(L, R, x);
if (k == 1) {
#ifdef ONLINE_JUDGE
*++__IO::W::ch = '-';
#else
putchar('-');
#endif
return inf;
}
else return gtkth(L, R, k - 1);
}
int nxt(int L, int R, int x) {
int k = gtrnk(L, R, x + 1);
if (k > R - L + 1) return inf;
else return gtkth(L, R, k);
}
} int n, m, V[maxn];
int main() {
// freopen("LG3380.in", "r", stdin);
// freopen("LG3380.txt", "w", stdout);
#ifdef ONLINE_JUDGE
__IO::R::begin();
#endif
srand(20040826);
n = read(), m = read();
for (int i = 1; i <= n; i++) {
V[i] = read();
SgT::insert(i, V[i]);
}
while (m --> 0) {
int op = read(), l = read(), r = read(), k;
if (op != 3) k = read();
switch (op) {
case 1:
write(SgT::gtrnk(l, r, k));
#ifdef ONLINE_JUDGE
*++__IO::W::ch = '\n';
#else
putchar('\n');
#endif
break;
case 2:
write(SgT::gtkth(l, r, k));
#ifdef ONLINE_JUDGE
*++__IO::W::ch = '\n';
#else
putchar('\n');
#endif
break;
case 3:
SgT::erase(l, V[l]);
V[l] = r;
SgT::insert(l, V[l]);
break;
case 4:
write(SgT::pre(l, r, k));
#ifdef ONLINE_JUDGE
*++__IO::W::ch = '\n';
#else
putchar('\n');
#endif
break;
case 5:
write(SgT::nxt(l, r, k));
#ifdef ONLINE_JUDGE
*++__IO::W::ch = '\n';
#else
putchar('\n');
#endif
break;
}
}
#ifdef ONLINE_JUDGE
__IO::W::end();
#endif
return 0;
}