希望大家别喷我但是我真的重构了挺多次的了。。。
目测操作 1/3 有锅,有巨辣帮忙吗/kel
#include <iostream>
#include <cstdlib>
#include <ctime>
#define MAXN 10000000
using namespace std;
int max(int x, int y) {return ((x > y) ? (x) : (y));}
int min(int x, int y) {return ((x < y) ? (x) : (y));}
//---QWQAQUQ---
int n, m, amin = 0x7f7f7f7f, amax = -0x7f7f7f7f;
//---QWQAQUQ---
struct node {
int val, ls, rs, siz, rnd;
} T[MAXN + 10];
int tot = 0;
int a[50000 + 10];
struct FHQ_traep {
int root;
void clear() {tot = root = 0;}
void updata(int now) {
T[now].siz = T[T[now].ls].siz + T[T[now].rs].siz + 1;
}
void split(int &x, int &y, int val, int now) {
if(!now) {x = y = 0; return;}
else if(T[now].val <= val) x = now, split(T[now].rs, y, val, T[now].rs);
else y = now, split(x, T[now].ls, val, T[now].ls);
updata(now);
}
int merge(int x, int y) {
if(!x || !y) return x | y;
if(T[x].rnd < T[y].rnd) {
T[x].rs = merge(T[x].rs, y);
updata(x); return x;
}
else {
T[y].ls = merge(x, T[y].ls);
updata(y); return y;
}
}
int New(int val) {
T[++tot].val = val;
T[tot].rnd = rand();
T[tot].siz = 1;
return tot;
}
void Insert(int val) {
int x, y, z;
split(x, y, val, root);
root = merge(merge(x, New(val)), y);
}
void Delete(int val) {
int x, y, z;
split(x, z, val, root);
split(x, y, val - 1, x);
y = merge(T[y].ls, T[y].rs);
root = merge(merge(x, y), z);
}
int Find_rank(int val) {
int x, y, ans = 0;
split(x, y, val - 1, root);
ans = T[x].siz + 1;
root = merge(x, y);
return ans;
}
int Find_val(int now, int rank) {
while(233) {
if(rank <= T[T[now].ls].siz) now = T[now].ls;
else if(rank == T[T[now].ls].siz + 1) return T[now].val;
else rank = rank - T[T[now].ls].siz - 1, now = T[now].rs;
}
}
int Pre(int val) {
int x, y, z, ans = 0;
split(x, y, val - 1, root);
if(T[x].siz) ans = Find_val(x, T[x].siz);
else ans = -2147483647;
merge(x, y);
return ans;
}
int Next(int val) {
int x, y, z, ans = 0;
split(x, y, val, root);
if(T[y].siz) ans = Find_val(y, 1);
else ans = 2147483647;
merge(x, y);
return ans;
}
} TT[50000 * 4 + 10];
//QWQAQUQ
int ls(int x) {return (x << 1);}
int rs(int x) {return (x << 1 | 1);}
int F_rank(int l, int r, int s, int t, int now, int val) {
if(l <= s && t <= r) return TT[now].Find_rank(val) - 1;
int mid = (s + t) >> 1, res = 0;
if(l <= mid) res += F_rank(l, r, s, mid, ls(now), val);
if(r > mid) res += F_rank(l, r, mid + 1, t, rs(now), val);
return res;
}
int F_val(int l, int r, int rank) {
int L = amin, R = amax, ans = 20090725;
while(L <= R) {
int mid = (L + R) >> 1;
if(F_rank(l, r, 1, n, 1, mid) + 1 <= rank) ans = mid, L = mid + 1;
else R = mid - 1;
}
return ans;
}
void T_updata(int l, int r, int pos, int now, int val) {
TT[now].Delete(a[pos]), TT[now].Insert(val);
int mid = (l + r) >> 1;
if(l == r) return ;
if(pos <= mid) T_updata(l, mid, pos, ls(now), val);
else T_updata(mid + 1, r, pos, rs(now), val);
}
int T_pre(int l, int r, int s, int t, int now, int val) {
if(l <= s && t <= r) return TT[now].Pre(val);
int mid = (s + t) >> 1, res = -2147483647;
if(l <= mid) res = max(res, T_pre(l, r, s, mid, ls(now), val));
if(r > mid) res = max(res, T_pre(l, r, mid + 1, t, rs(now), val));
return res;
}
int T_next(int l, int r, int s, int t, int now, int val) {
if(l <= s && t <= r) return TT[now].Next(val);
int mid = (s + t) >> 1, res = 2147483647;
if(l <= mid) res = min(res, T_next(l, r, s, mid, ls(now), val));
if(r > mid) res = min(res, T_next(l, r, mid + 1, t, rs(now), val));
return res;
}
void build(int l, int r, int now) {
for(int p = l; p <= r; p++) TT[now].Insert(a[p]);
int mid = (l + r) >> 1;
if (l != r) {
build(l, mid, ls(now));
build(mid + 1, r, rs(now));
}
return;
}
//---QWQAQUQ---
int main() {
srand(time(0));
cin >> n >> m;
for(int p = 1; p <= n; p++) {
cin >> a[p];
amin = min(amin, a[p]);
amax = max(amax, a[p]);
}
build(1, n, 1);
int opt, x, y, z;
while(m--) {
cin >> opt >> x >> y;
if(opt == 1) cin >> z, cout << F_rank(x, y, 1, n, 1, z) + 1 << endl;
else if(opt == 2) cin >> z, cout << F_val(x, y, z) << endl;
else if(opt == 3) T_updata(1, n, x, 1, y);
else if(opt == 4) cin >> z, cout << T_pre(x, y, 1, n, 1, z) <<endl;
else if(opt == 5) cin >> z, cout << T_next(x, y, 1, n, 1, z) << endl;
}
}