#include <iostream>
#define MAXN 100000
#define INF 0x7f7f7f7f
#define QWQ cout << "QWQ" << endl;
using namespace std;
struct Splay {
#define root T[0].son[1]
struct node{
int val,fa,siz,son[2],cnt;
}T[MAXN+10];
int tot;
int LorR(int x) {
return ((T[T[x].fa].son[0] == x)?(0):(1));
}
void connect(int x,int fa,int vis) {
T[fa].son[vis] = x;
T[x].fa = fa;
}
void updata(int x) {
T[x].siz = T[T[x].son[0]].siz + T[T[x].son[1]].siz + T[x].cnt;
}
void rotate(int x) {
int y = T[x].fa,r = T[T[x].fa].fa;
int ys = LorR(x),rs = LorR(y),B = T[x].son[ys^1];
connect(B,y,ys),connect(y,x,ys^1),connect(x,r,rs);
updata(y),updata(x);
}
void splay(int x,int to) {
to = T[to].fa;
while(T[x].fa != to) {
cout << T[x].fa << ' ' << to << endl;
if(to == T[T[x].fa].fa) rotate(x);
else if(LorR(x) == LorR(T[x].fa)) rotate(T[x].fa),rotate(x);
else rotate(x),rotate(x);
}
}
int New(int val,int fa) {
T[++tot].fa = fa,T[tot].val =val;
T[tot].siz = T[tot].cnt = 1;
return tot;
}
void find(int val) {
int now = root;
while(T[now].son[((val < T[now].val)?(0):(1))] && val != T[now].val)
now = T[now].son[((val < T[now].val)?(0):(1))];
splay(now,root);
}
void insert(int val) {
int now = root;
if(!now)
root = New(val,root);
else {
while(233) {
cout << now << endl;
T[now].siz++;
if(T[now].val == val) {
cout << "type1" << endl;
T[now].cnt++;
splay(now,root);
return ;
}
int next = ((val < T[now].val)?(0):(1));
if(!T[now].son[next]) {
cout << "type2" << endl;
T[now].son[next] = New(val,now);
QWQ
splay(tot,root);
QWQ
return ;
}
now = T[now].son[next];
}
}
}
int low_up(int val,int f) {
find(val);
cout << root << ' ' << T[root].val << endl;
if(T[root].val > val && f) return root;
if(T[root].val < val && !f) return root;
int now = T[root].son[f];
while(T[now].son[f ^ 1])
now = T[now].son[f ^ 1];
return now;
}
int upper(int val) {
return T[low_up(val,0)].val;
}
int lower(int val) {
return T[low_up(val,1)].val;
}
int find_rank(int val) {
find(val);
return T[T[root].son[0]].siz;
}
int find_val(int rank) {
int now = root;
while(233) {
if(rank <= T[T[now].son[0]].siz) now = T[now].son[0];
else if(rank <= T[T[now].son[0]].siz + T[now].cnt) return T[now].val;
else rank = rank - T[T[now].son[0]].siz - T[now].cnt, now = T[now].son[1];
}
}
void clear(int x) {
T[x].cnt = T[x].siz = T[x].son[0] = T[x].son[1] = T[x].val = T[x].fa = 0;
}
void erase(int val) {
int pre = low_up(val,0), low = low_up(val,1);
splay(pre,root),splay(low,pre);
int u = T[low].son[0];
if(T[u].cnt > 1) {
T[u].cnt--;
splay(u,root);
}
else clear(T[low].son[0]);
tot--;
}
}qwq;
int main() {
qwq.insert(INF);
qwq.insert(-INF);
int T,opt,val;
cin >> T;
while(T--) {
cin >> opt >> val;
if(opt == 1) qwq.insert(val);
else if(opt == 2) qwq.erase(val);
else if(opt == 3) cout << qwq.find_rank(val) << endl;
else if(opt == 4) cout << qwq.find_val(val+1) << endl;
else if(opt == 5) cout << qwq.upper(val) << endl;
else if(opt == 6) cout << qwq.lower(val) << endl;
}
}
下了第三个点的数据,虽说是 TLE 但是好像也错了/ch
有些东西是我调试的,请大家自行忽略
求助/kk/kk/kk