不会调,求dalao帮帮
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct Treap {
int l, r;
int key, pri; //插入的数,优先级
int size;
} t[N];
int cnt, root, n;
void New(int x) {
t[++cnt].size = 1;
t[cnt].l = t[cnt].r = 0;
t[cnt].key = x;
t[cnt].pri = rand();
}
void push_up(int u) {
t[u].size = t[t[u].l].size + t[t[u].r].size + 1;
}
void rotate(int &o, int d) { //d=0右旋,d=1左旋
int k;
if (d) {
k = t[o].r;
t[o].r = t[k].l;
t[k].l = o;
t[k].size = t[o].size;
t[o].size=t[o].size-(t[t[o].r].size+1);
} else {
k = t[o].l;
t[o].l = t[k].r;
t[k].r = o;
t[k].size = t[o].size;
t[o].size=t[o].size-(t[t[o].l].size+1);
}
push_up(o);
o = k;
}
void Insert(int &u, int x) {
if (!u) {
New(x);
u = cnt;
return ;
}
t[u].size++;
if (x >= t[u].key)Insert(t[u].r, x);
else Insert(t[u].l, x);
if (t[u].l && t[u].pri > t[t[u].l].pri)rotate(u, 0);
if (t[u].r && t[u].pri > t[t[u].r].pri)rotate(u, 1);
push_up(u);
}
void Del(int &u, int x) { //删
t[u].size--;
if (t[u].key == x) {
if (!t[u].l && !t[u].r) {
u = 0;
return ;
}
if (!t[u].l || !t[u].r) {
u = t[u].l + t[u].r;
return ;
}
if (t[t[u].l].pri < t[t[u].r].pri) {
rotate(u, 0);
Del(t[u].r, x);
return ;
} else {
rotate(u, 1);
Del(t[u].l, x);
return ;
}
if (t[u].key >= x)Del(t[u].l, x);
else Del(t[u].r, x);
push_up(u);
}
}
int Rank(int u, int x) {
if (!u)return 0;
if (x > t[u].key)return t[t[u].l].size + 1 + Rank(t[u].r, x);
return Rank(t[u].l, x);
}
int kth(int u, int k) {
if (k == t[t[u].l].size + 1)return t[u].key;
if (k > t[t[u].l].size + 1)return kth(t[u].r, k - t[t[u].l].size - 1);
if (k <= t[t[u].l].size) return kth(t[u].l, k);
}
int Find_pri(int u, int x) {
if (!u)return 0;
if (t[u].key >= x)return Find_pri(t[u].l, x);
int val = Find_pri(t[u].r, x);
if (!val)return t[u].key;
return val;
}
int Find_nxt(int u, int x) {
if (!u)return 0;
if (t[u].key <= x)return Find_nxt(t[u].r, x);
int val = Find_nxt(t[u].l, x);
if (!val)return t[u].key;
return val;
}
int main() {
srand(time(NULL));
cin >> n;
while (n--) {
int opt, x;
cin >> opt >> x;
switch (opt) {
case 1:
Insert(root, x);
break;
case 2:
Del(root, x);
break;
case 3:
cout << Rank(root, x) + 1 << endl;
break;
case 4:
cout << kth(root, x) << endl;
break;
case 5:
cout << Find_pri(root, x) << endl;
break;
case 6:
cout << Find_nxt(root, x) << endl;
break;
}
}
return 0;
}