学步园

每个数字的值是tr[k].num+delta

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<ctime>
using namespace std;
struct data{
	int l,r,num,rnd,s;
}tr[100001];
int n,Min,root,size,leave,delta,X;
char oper[1];
void update(int k){
	tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;
}
void rrotate(int &k){
     int t=tr[k].l;
     tr[k].l=tr[t].r;
     tr[t].r=k;
     tr[t].s=tr[k].s;
     update(k);
     k=t;
}
void lrotate(int &k){
     int t=tr[k].r;
     tr[k].r=tr[t].l;
     tr[t].l=k;
     tr[t].s=tr[k].s;
     update(k);
     k=t;
}
void insert(int &k,int x){
	if(k==0){
		tr[k=++size].rnd=rand();
		tr[k].num=x;tr[k].s=1;
		return;
	}
	tr[k].s++;
	if(x<tr[k].num){
		insert(tr[k].l,x);
		if(tr[tr[k].l].rnd<tr[k].rnd)rrotate(k);
	}
	else{
		insert(tr[k].r,x);
		if(tr[tr[k].r].rnd<tr[k].rnd)lrotate(k);
	}
}
int del(int &k,int x){
	int t;
	if(k==0)return 0;
	if(tr[k].num<x){
		t=tr[tr[k].l].s+1;
		k=tr[k].r;
		return t+del(k,x);
	}
	else{
		t=del(tr[k].l,x);
		tr[k].s-=t;
		return t;
	}
}
int find(int k,int x)
{
    if(tr[tr[k].l].s+1==x)return tr[k].num+delta;
    else if(tr[tr[k].l].s+1<x)return find(tr[k].r,x-tr[tr[k].l].s-1);
    else return find(tr[k].l,x);
}
int main(){
	//srand(time(0));
	scanf("%d%d",&n,&Min);
	while(n--){
		scanf("%s%d",oper,&X);
		switch(oper[0]){
			case 'I':{
				if(X>=Min)insert(root,X-delta);
				break;
			}
			case 'A':{
				delta+=X;
				break;
			}
			case 'S':{
				delta-=X;
				leave+=del(root,Min-delta);
				break;
			}
			case 'F':{
				if(X>tr[root].s)printf("-1\n");
				else printf("%d\n",find(root,tr[root].s-X+1));
				break;
			}
		}
	}
	printf("%d\n",leave);
	return 0;
}