60分

#6 WA

#7-#10 TLE

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,opt,x,root,tot = 0;
struct node{
	int l,r,v,p,siz;
}tr[N<<2];
stack<int>rab;
int creat(int v){
	int x;
	if(!rab.empty()){
		x = rab.top();
		rab.pop();
	}else{
    	x = ++tot;
	}
	tr[x].v = v;
	tr[x].p = 1ll * rand() * rand() % 2100000000;
	tr[x].siz = 1;
	return x;
}
void update(int x){
	tr[x].siz = tr[tr[x].l].siz + tr[tr[x].r].siz + 1;
}
void split(int now,int v,int &x,int &y){
	
	if(!now){
		x = y = 0;
		return ;
	}
	if(tr[now].v <= v){
		x = now;
		split(tr[now].r, v, tr[now].r, y);
	}else{
		y = now;
		split(tr[now].l, v, x, tr[now].l);
	}
	update(now);
}
int merge(int x,int y){
	if((!x) || (!y)){
		return x | y;
	}
	if(tr[x].p > tr[y].p){
		tr[x].r = merge(tr[x].r,y);
		update(x);
		return x;
	}else{
		tr[y].l = merge(x,tr[y].l);
		update(y);
		return y;
	}
}
void insert(int v){
	if(root == 0){
		root = creat(v);
		return ;
	}
	int x,y;
	split(root,v - 1,x,y);
	root = merge(merge(x,creat(v)),y);
}
void delet(int v){
	int x,y,z;
	split(root,v - 1,x,y);
	split(y,v,y,z);
	rab.push(y);
	y = merge(tr[y].l,tr[y].r);
	root = merge(x,merge(y,z));
}
int fx(int v){
	int x,y;
	split(root,v - 1,x,y);
	int ans =  tr[x].siz;
	root = merge(x,y);
	return ans + 1;
}
int fk(int r){
	int now = root;
	int a = 0;
	while(1){
		a++;
		if(tr[tr[now].l].siz + 1 == r){
			return tr[now].v;
		}else if(tr[tr[now].l].siz + 1 < r){
			r = r - tr[tr[now].l].siz - 1;
			now = tr[now].r;
			
		}else if(tr[tr[now].l].siz + 1 > r){
			now = tr[now].l;
		}
	}
}
int pre(int v){
	int x,y;
	split(root,v - 1,x,y);
	int now = x;
	while(tr[now].r) now = tr[now].r;
	int ans = tr[now].v;
	root = merge(x,y);
	return ans;
}
int nxt(int v){
	int x,y;
	split(root,v,x,y);
	int now = y;
	while(tr[now].l) now = tr[now].l;
	int ans = tr[now].v;
	root = merge(x,y);
	return ans;
}
void print(){
	cout<<root<<'\n';
	for(int i = 0;i <= tot; ++i){
		cout<<i<<' '<<tr[i].l<<' '<<tr[i].r<<' '<<tr[i].v<<' '<<tr[i].siz<<' '<<tr[i].p<<'\n';
	}
}
void op(){
	cin>>n;
	for(int i = 1;i <= n; ++i){
		cin>>opt>>x;
		if(opt == 1){
			insert(x);
		}else if(opt == 2){
			delet(x);			
		}else if(opt == 3){
			cout<<fx(x)<<'\n';
		}else if(opt == 4){
			cout<<fk(x)<<'\n';
		}else if(opt == 5){
			cout<<pre(x)<<'\n';
		}else if(opt == 6){
			cout<<nxt(x)<<'\n';
		}
		// print();
	}
}
int main(){
	srand(20070727);
	op();
	return 0;
}