```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson t << 1, l, m
#define rson t << 1 | 1, m + 1, r
typedef long long ll;
#define $(i, a, n) for(int i = a; i <= n; ++i)
using namespace std;
inline ll read() {
ll ans = 0;
char ch = getchar(), last = ' ';
while (ch < '0' || ch > '9') last = ch, ch = getchar();
while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
if (last == '-') return -ans;
return ans;
}
const int INF = 0x3f3f3f3f;
const int N = 5e4 + 5;
int a[N];
namespace Treap{
const int MAXN = 2e6 + 15; //原来是1e6
struct node{
int l, r, v, key, size;
}z[MAXN];
int cnt = 0;
void update(int x) {
z[x].size = z[z[x].l].size + z[z[x].r].size + 1;
}
int newnode(int v) {
z[++cnt].key = rand();
z[cnt].l = z[cnt].r = 0;
z[cnt].v = v;
z[cnt].size = 1;
return cnt;
}
int merge(int x, int y) {
if (x == 0 || y == 0) return x | y;
if (z[x].key > z[y].key) {
z[x].r = merge(z[x].r, y);
update(x);
return x;
} else {
z[y].l = merge(x, z[y].l);
update(y);
return y;
}
}
pair<int, int> split_v(int x, int v) {
if (x == 0) return make_pair(0, 0);
if (z[x].v > v) {
pair<int, int> p = split_v(z[x].l, v);
z[x].l = p.second;
update(x);
return make_pair(p.first, x);
} else {
pair<int, int> p = split_v(z[x].r, v);
z[x].r = p.first;
update(x);
return make_pair(x, p.second);
}
}
void insert(int &root, int v) {
pair<int, int> p = split_v(root, v - 1);
root = merge(merge(p.first, newnode(v)), p.second);
}
void del(int &root, int v) {
pair<int, int> p = split_v(root, v);
pair<int, int> p2 = split_v(p.first, v - 1);
p2.second = merge(z[p2.second].l, z[p2.second].r);
root = merge(merge(p2.first, p2.second), p.second);
}
int kth(int x, int k) {
if (z[z[x].l].size >= k) {
return kth(z[x].l, k);
} else {
if(z[z[x].l].size + 1 == k) return z[x].v;
return kth(z[x].r, k - z[z[x].l].size - 1);
}
}
int rnk(int &root, int v) {
pair<int, int> p = split_v(root, v - 1);
int ans = z[p.first].size + 1;
root = merge(p.first, p.second);
return ans;
}
int pre(int &root, int v) {
pair<int, int> p = split_v(root, v - 1);
int ans = -2147483647;
if(p.first) ans = kth(p.first, z[p.first].size);
root = merge(p.first, p.second);
return ans;
}
int suf(int &root, int v) {
pair<int, int> p = split_v(root, v);
int ans = 2147483647;
if(p.second) ans = kth(p.second, 1);
root = merge(p.first, p.second);
return ans;
}
}
namespace SEG{
struct node{
int l, r;
int root;
}z[N << 2];
void build(int t, int l, int r) {
z[t].l = l, z[t].r = r;
for (int i = l; i <= r; ++i) {
Treap::insert(z[t].root, a[i]);
}
if(l >= r) return;
int m = (l + r) >> 1;
build(lson);
build(rson);
}
void modify(int t, int x, int v) {
Treap::del(z[t].root, a[x]);
Treap::insert(z[t].root, v);
if (z[t].l == z[t].r) return;
int m = (z[t].l + z[t].r) >> 1;
if (x <= m) modify(t << 1, x, v);
else modify(t << 1 | 1, x, v);
}
int queryRank(int t, int l, int r, int v) {
if (l <= z[t].l && z[t].r <= r) return Treap::rnk(z[t].root, v) - 1;
int ans = 0;
int m = (z[t].l + z[t].r) >> 1;
if (l <= m) ans += queryRank(t << 1, l, r, v);
if (r > m) ans += queryRank(t << 1 | 1, l, r, v);
return ans;
}
int queryKth(int t, int l, int r, int k) {
int L = 0, R = 1e8;
int ans = 0;
while (L <= R) {
int mid = (L + R) >> 1;
int rk = queryRank(t, l, r, mid);
if(rk + 1 <= k) {
ans = mid;
L = mid + 1;
} else R = mid - 1;
}
return ans;
}
int queryPre(int t, int l, int r, int v) {
if(l <= z[t].l && z[t].r <= r) return Treap::pre(z[t].root, v);
int ans = -2147483647;
int m = (z[t].l + z[t].r) >> 1;
if (l <= m) ans = max(ans, queryPre(t << 1, l, r, v));
if (r > m) ans = max(ans, queryPre(t << 1 | 1, l, r, v));
return ans;
}
int querySuf(int t, int l, int r, int v) {
if(l <= z[t].l && z[t].r <= r) return Treap::suf(z[t].root, v);
int ans = 2147483647;
int m = (z[t].l + z[t].r) >> 1;
if (l <= m) ans = min(ans, querySuf(t << 1, l, r, v));
if (r > m) ans = min(ans, querySuf(t << 1 | 1, l, r, v));
return ans;
}
}
int n, m;
int main() {
// freopen("input8.in", "r", stdin);
// freopen("ans.out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
SEG::build(1, 1, n);
int op, l, r, k;
for(int i = 1; i<= m; ++i) {
op = read();
if (op != 3) l = read(), r = read(), k = read();
else l = read(), k = read();
if (op == 1) printf("%d\n", SEG::queryRank(1, l, r, k) + 1);
else if (op == 2) printf("%d\n", SEG::queryKth(1, l, r, k));
else if (op == 3) SEG::modify(1, l, k), a[l] = k;
else if (op == 4) printf("%d\n", SEG::queryPre(1, l, r, k));
else printf("%d\n", SEG::querySuf(1, l, r, k));
}
return 0;
}
```
by Stream月 @ 2019-12-22 22:06:35
数组我是开80W，没有WA的点，但是因为是套splay，常数太大T的起飞
by 老咸鱼了 @ 2019-12-22 22:19:30
@[帅气伙小](/user/155626) ~~fhqtreqp真香~~
by Stream月 @ 2019-12-22 22:27:54
@[Stream月](/user/156945) 我头铁
by 老咸鱼了 @ 2019-12-22 23:07:25
@[Stream月](/user/156945) 您的```read()```其实比带```#include<stdio.h>```的```scanf```还慢。
试试**fread**？
```cpp
const static int _ = 1 << 20 ;
char fin[_] , * p1 = fin , * p2 = fin ;
inline char gc() { return (p1 == p2) && (p2 = (p1 = fin) + fread(fin , 1 , _ , stdin) , p1 == p2) ? EOF : * p1 ++ ; }
inline int read() {
bool sign = 1 ; char c = 0 ; while(c < 48) ((c = gc()) == 45) && (sign = 0) ;
int x = (c & 15) ; while((c = gc()) > 47) x = (x << 1) + (x << 3) + (c & 15) ;
return sign ? x : -x ;
}
```
对于$10^8$以上的数据规模，速度至少比带```#include<stdio.h>```的```scanf```快1倍。
by jwcub @ 2019-12-23 19:19:19