记录编号	424026	评测结果	AAAAAAAAAA
题目名称	[NOI 2004]郁闷的出纳员	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	1.313 s
提交时间	2017-07-12 19:44:38	内存使用	6.04 MiB

#include<stdio.h>
#include<iostream>
#include<ctime>
#include<cmath>
#include<cstdlib>
#define maxn 250005
#define inf 10000000
using namespace std;
int zz,n,m,root,lazy,go,o;
char c;
struct tree{
       int l,r,no;
       int size,tot,rd;
       }t[maxn];             
void l_swap(int &now){
     int newnow=t[now].r;
     t[now].r=t[newnow].l;
     t[newnow].l=now;
     t[newnow].size=t[now].size;
     t[now].size=t[t[now].l].size+t[t[now].r].size+1;
     now=newnow;
}
void r_swap(int &now){
     int newnow=t[now].l;
     t[now].l=t[newnow].r;
     t[newnow].r=now;
     t[newnow].size=t[now].size;
     t[now].size=t[t[now].l].size+t[t[now].r].size+1;
     now=newnow;
}
void buildtree(int &root,int x){
    if(!root){
        root=++zz;
        t[root].no=x;
        t[root].size=1;
        t[root].tot=1;
        t[root].rd=rand();
        return ;
    }
    t[root].size++;
    if(x<t[root].no){
        buildtree(t[root].l,x);
        if(t[t[root].l].rd<t[root].rd) 
           r_swap(root);
    }
    else{
        buildtree(t[root].r,x);
        if(t[t[root].r].rd<t[root].rd) 
           l_swap(root);
    }
}
int ask_rank_num(int root,int rank){
    if(t[t[root].l].size+1==rank) 
       return t[root].no+lazy;
    if(t[t[root].l].size+1<rank) 
       return ask_rank_num(t[root].r,rank-t[t[root].l].size-1);
    return ask_rank_num(t[root].l,rank);
}
int delete_x(int &root,int x){
    if(!root) return 0 ;
    if(t[root].no<x){
        int tot=1+t[t[root].l].size;
        root=t[root].r; 
        return tot+delete_x(root,x);
    }
    else{
        int tot=delete_x(t[root].l,x);
        t[root].size-=tot; 
        return tot;
    }
}
int main(){
    freopen("cashier.in","r",stdin);
    freopen("cashier.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        cin>>c>>o;
        if(c=='I'){ 
           if(o>=m)
              buildtree(root,o-lazy);
        }
        if(c=='F'){
            //cout<<"*******"<<t[root].size<<" ";
            if(o>t[root].size) printf("-1\n");
            else printf("%d\n",ask_rank_num(root,t[root].size-o+1)); 
        }
        if(c=='A') lazy+=o;
        if(c=='S'){
            lazy-=o;
            go+=delete_x(root,m-lazy);
        }
    }
    printf("%d",go);
    //system("pause");
    return 0;
}