#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;
const int maxn = 2e6 + 10;
struct node {
int s[2],size,val,p,cnt;
void init(int parent,int w){
size = cnt = 1,val = w,p = parent;
}
void clear(){
s[0] = s[1] = val = size = p = cnt = 0;
}
}tr[maxn];
int n,m,tot,root;
bool f;char c;
inline void R(int &x){
x = 0,f = 0;c = getchar();
while (c < '0' || c > '9'){ if (c == '-') f = 1; c = getchar();}
while (c >='0' && c <= '9'){ x = (x << 3) + (x << 1) + (c & 15);c = getchar();}
if (f) x = -x;
}
inline void pushup(int q){
tr[q].size = tr[tr[q].s[0]].size + tr[tr[q].s[1]].size + tr[q].cnt;
}
inline void rotate(int q){
int y = tr[q].p ,z = tr[y].p;
int son = tr[y].s[1] == q;
tr[y].s[son] = tr[q].s[son ^ 1];
tr[tr[q].s[son ^ 1]].p = y;
tr[q].s[son ^ 1] = y;
tr[y].p = q;
tr[q].p = z;
tr[z].s[tr[z].s[1] == y] = q;
pushup(y),pushup(q);
}
inline void splay(int q,int tar){
int y,z;
while (tar ^ tr[q].p){
y = tr[q].p,z = tr[y].p;
if (z ^ tar){
if ((y == tr[z].s[0]) ^ (q == tr[y].s[0])) rotate(q) ;
else rotate(y);
}
rotate(q);
}
if (!tar) root = q;
}
inline void find(int x){
int q = root ;
while (tr[q].s[x > tr[q].val] && (x ^ tr[q].val) )
q = tr[q].s[x > tr[q].val];
splay(q,0);
}
inline void add(int x){
int q = root,p = 0;
while (q && (tr[q].val ^ x)) p = q,q = tr[q].s[tr[q].val < x];
if (q) ++tr[q].cnt;
else
q = ++tot,tr[p].s[tr[p].val < x] = q,tr[q].init(p,x);
splay(q,0);
}
inline int get_pre(int x){
find(x);
int q = root;
if (tr[q].val < x) return q;
q = tr[q].s[0];
while (tr[q].s[1]) q = tr[q].s[1];
splay(q,0);
return q;
}
inline int get_suf(int x){
find(x);
int q = root;
if (tr[q].val > x) return q;
q = tr[q].s[1];
while (tr[q].s[0]) q = tr[q].s[0];
splay(q,0);
return q;
}
inline void del(int x){
int pre = get_pre(x),suf = get_suf(x);
splay(pre,0),splay(suf,pre);
int q = tr[suf].s[0];
if (tr[q].cnt > 1)
--tr[q].cnt,splay(q,0);
else
tr[suf].s[0] = 0,splay(suf,0);
}
inline int get_k(int k){
int q = root ;
while (1){
if (tr[tr[q].s[0]].size + tr[q].cnt < k)
k -= tr[tr[q].s[0]].size + tr[q].cnt,q = tr[q].s[1];
else if (tr[tr[q].s[0]].size >= k) q = tr[q].s[0];
else break ;
}
splay(q,0);
return tr[q].val;
}
inline int get_rk(int x){ // 如果用find(x) ; return tr[tr[root].s[0]].size ; 的方法会T,也会wa
int q = root,res =0;
while(q){
if(tr[q].val == x){
res += tr[tr[q].s[0]].size; //这里的res不能放到splay后,因为splay后,q的左右子树都会变
splay(q,0); return res ;
}
if(tr[q].val>x)
q = tr[q].s[0];
else
res += tr[tr[q].s[0]].size + tr[q].cnt,q = tr[q].s[1];
}
splay((tr[q].val == x ? q : tr[q].p),0);
return res;
}
int main(){
// freopen("a.in","r",stdin);
R(n),R(m);
add(2e9);add(-2e9);
for (int i = 1,t ; i <= n ; ++i)
R(t),add(t);
int last = 0,res = 0;
for (int i = 1,op,x; i <= m ; ++i){
R(op),R(x);
x ^= last;
if (op == 1)
add(x);
else if (op == 2)
del(x);
else if (op == 3)
last = get_rk(x);
else if (op == 4)
last = get_k(x + 1);
else if (op == 5)
last = tr[get_pre(x)].val;
else if (op == 6)
last = tr[get_suf(x)].val;
if (op >= 3)
res ^= last;
}
printf("%d",res);
return 0;
}
P3369
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 2e6 + 10;
struct node {
int s[2],val,cnt,size,p;
void init(int parent,int v){
val = v,p = parent ;
cnt = size = 1;
}
}tr[maxn];
int root,tot,n;
inline void pushup(int q){
tr[q].size = tr[tr[q].s[0]].size + tr[tr[q].s[1]].size + tr[q].cnt ;
}
inline void rotate(int q){
int p = tr[q].p , pp = tr[p].p,son = tr[p].s[1] == q;
tr[pp].s[tr[pp].s[1] == p] = q;
tr[q].p = pp;
tr[p].s[son] = tr[q].s[son ^ 1];
tr[tr[q].s[son ^ 1]].p = p;
tr[p].p = q;
tr[q].s[son ^ 1] = p;
pushup(p),pushup(q);
}
inline void splay(int q,int tar){
int p,pp;
while (tr[q].p ^ tar){
p = tr[q].p, pp = tr[p].p;
if (pp ^ tar)
((tr[p].s[0] == q) ^ (tr[pp].s[0] == p)) ? rotate(q) : rotate(p);
rotate(q);
}
if (!tar) root = q;
}
inline void find(int x){
int q = root ;
while (tr[q].s[tr[q].val < x] && (tr[q].val ^ x)) q = tr[q].s[tr[q].val < x];
splay(q,0);
}
inline void add(int x){
int q = root, p = 0;
while (q && (tr[q].val ^ x)) p = q,q = tr[q].s[tr[q].val < x];
if (q)
++tr[q].cnt ;
else
q = ++tot,tr[p].s[tr[p].val < x] = q,tr[q].init(p,x);
splay(q,0);
}
inline int get_pre(int x){
find(x);
int q = root;
if (tr[q].val < x) return q;
q = tr[q].s[0];
while (tr[q].s[1]) q = tr[q].s[1];
splay(q,0);
return q;
}
inline int get_suf(int x){
find(x);
int q = root ;
if (tr[q].val > x) return q;
q = tr[q].s[1];
while (tr[q].s[0]) q = tr[q].s[0];
splay(q,0);
return q;
}
inline int get_k(int k){
int q = root ;
while (q){
if (tr[q].cnt + tr[tr[q].s[0]].size < k) k -= tr[q].cnt + tr[tr[q].s[0]].size,q = tr[q].s[1];
else if (tr[tr[q].s[0]].size >= k) q = tr[q].s[0];
else break;
}
splay(q,0);
return tr[q].val;
}
inline int get_rk(int x){
int q = root,res = 0;
while (q){
if (tr[q].val == x){
res += tr[tr[q].s[0]].size,splay(q,0);
return res ;
}else if (tr[q].val < x)
res += tr[q].cnt + tr[tr[q].s[0]].size,q = tr[q].s[1];
else
q = tr[q].s[0];
}
splay(tr[q].val == x ? q : tr[q].p,0);
return res;
}
inline void del(int x){
int pre = get_pre(x),suf = get_suf(x);
splay(pre,0),splay(suf,pre);
if (tr[tr[suf].s[0]].cnt > 1)
--tr[tr[suf].s[0]].cnt,splay(tr[suf].s[0],0) ;
else
tr[suf].s[0] = 0,splay(suf,0);
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
add(1e9),add(-1e9);
for (int i = 1,op,x; i <= n ; ++i){
cin >> op >> x;
if (op == 1)
add(x);
else if (op == 2)
del(x);
else if (op == 3)
cout << get_rk(x) << '\n';
else if (op == 4)
cout << get_k(x + 1) << '\n';
else if (op == 5)
cout << tr[get_pre(x)].val << '\n';
else if (op == 6)
cout << tr[get_suf(x)].val << '\n';
}
return 0;
}