题目链接

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 3e5 + 10;
int tot,rt;
struct Treap{
	int siz[MAXN],pos[MAXN],son[MAXN][2],w[MAXN];
	bool tag[MAXN];
	int build(int x){
        w[++tot]=x;
		siz[tot]=1;
		pos[tot]=rand();
        return tot;
    }
	void push(int x){
		siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
	}
	void down(int x){
		swap(son[x][0],son[x][1]);
		if(son[x][0]) tag[son[x][0]]^=1;
		if(son[x][1]) tag[son[x][1]]^=1;
		tag[x]=0;
	}
	int merge(int x,int y){
		if(!x||!y){
			return x+y;
		}
		if(pos[x]<pos[y]){
			if(tag[x]) down(x);
			son[x][1]=merge(son[x][1],y);
			push(x);
			return x;
		}
		else{
			if(tag[y]) down(y);
			son[y][0]=merge(x,son[y][0]);
			push(y);
			return y;
		}
	} 
	void split(int i,int k,int &x,int &y){
		if(!i){
			x=y=0;
			return;
		}
		if(tag[i]) down(i);
		if(siz[son[i][0]]<k){
			x=i,split(son[x][1],k-siz[son[x][0]]+1,son[i][1],y);
		}
		else{
			y=i,split(son[i][0],k,x,son[i][0]);
			push(i);
		}
		return;
	}
}Tree;
int main(){
	int n,min;
	scanf("%d%d",&n,&min);
	for(int i=1;i<=n;i++){
		char op;
		int x,a,b;
		scanf(" %c%d",&op,&x);
		if(op=='I'){
			rt=Tree.merge(rt,Tree.build(x));
		}
		else if(op=='A'){
			for(int i=1;i<=tot;i++){
				Tree.w[i]+=x;
			}
		}
		else if(op=='S'){
			for(int i=1;i<=tot;i++){
				Tree.w[i]-=x;
			}
		}
		else if(op=='F'){
			Tree.split(rt,x,a,b);
			printf("%d\n",b);
		}
	}
}