题目通道（TREAP）

#include <bits/stdc++.h>
using namespace std;
int cnt=0,root=0,fire=0,prefire=0;
struct oi{
	int val,pri,size,lc,rc;
	int out,amo;
}tr[400001];
int node(int val){
	//cout<<"NEWNODEVAL:"<<val<<endl;
	tr[++cnt].val=val;
	tr[cnt].pri=rand();
	tr[cnt].lc=tr[cnt].rc=0;
	tr[cnt].size=tr[cnt].amo=1;
	tr[cnt].out=0;
	return cnt;
}
void pushup(int p){
	tr[p].size=tr[tr[p].lc].size+tr[tr[p].rc].size+tr[p].amo;
}
void zig(int &p)//right flip
{
	int q=tr[p].lc;
	tr[p].lc=tr[q].rc;
	tr[q].rc=p;
	tr[q].size=tr[p].size;
	pushup(p);
	p=q;
}
void zag(int &p){
	int q=tr[p].rc;
	tr[p].rc=tr[q].lc;
	tr[q].lc=p;
	tr[q].size=tr[p].size;
	pushup(p);
	p=q;
}
void insert(int &p,int val){
	if (!p){
		p=node(val);
		return ;
	}
	tr[p].size++;
	if (val==tr[p].val)    {
	    tr[p].amo++;
	    return ;
	}
	if (val<tr[p].val){
		insert(tr[p].lc,val);
		if (tr[p].pri<tr[tr[p].lc].pri)    zig(p);
	}
	if (val>tr[p].val){
		insert(tr[p].rc,val);
		if (tr[p].pri<tr[tr[p].rc].pri)    zag(p);
	}
	pushup(p);
}
void dele(int &p,int val){
	if (!p)    return ;
	tr[p].size--;
	if (val==tr[p].val){
		if (tr[p].amo>1)    {
		    tr[p].amo=0;
		}
		if (!tr[p].lc||!tr[p].lc){
			p=tr[p].lc+tr[p].rc; 
		} 
		else if (tr[tr[p].lc].pri>tr[tr[p].rc].pri){
				zig(p);
				dele(tr[p].rc,val);
			} else {
				zag(p);
				dele(tr[p].lc,val);
			}
		return ;
	}
	if (val<tr[p].val){
		dele(tr[p].lc,val);
	} else {
		dele(tr[p].rc,val);
	}
}
int derank(int p,int val){
	if (!p)    return 0;
	if (tr[tr[p].lc].size>=val)    return derank(tr[p].lc,val);
	if (tr[tr[p].lc].size+tr[p].amo>=val)
	    return tr[p].val;
	return derank(tr[p].rc,val-tr[tr[p].lc].size-tr[p].amo);
}
int main()
{
	int n,k;
	cin>>n>>k;
	for (int i=1;i<=n;i++)
	{
		char c;int m;
		cin>>c>>m;
		if (c=='I'){
			if (m<k)    {prefire++;}
		    else insert(root,m);
		}
		if (c=='A'){
			for (int i=1;i<=cnt;i++){
				if (tr[i].out==0)   tr[i].val+=m; 
			}
		}
		if (c=='S'){
			for (int i=1;i<=cnt;i++)
			{
				if (tr[i].out==0){
					//cout<<"pre_val:"<<tr[i].val<<" ";
    				tr[i].val-=m;
					if (tr[i].val<k){
						tr[i].out=1;
						dele(root,tr[i].val);
						//cout<<i<<" ";
						fire++;
					}
					//cout<<endl;
				}
				//cout<<endl;
			}
		}
		if (c=='F'){
			//cout<<"cnt:"<<cnt<<" fire:"<<fire<<" m:"<<m<<" ans:"<<cnt-m-fire+1<<endl;
			
			if (cnt-fire<m)    cout<<-1<<endl;
			
			else cout<<derank(root,cnt-m-fire+1)<<endl;
		} 
		//cout<<"cnt:"<<cnt<<endl;
	}
	//cout<<"*"<<prefire<<"*"<<fire<<endl;
    cout<<fire+prefire<<endl;
	return 0;
}

题目通道（TREAP）

题目通道（TREAP）