1503: [NOI2004]郁闷的出纳员

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 using namespace std;
  5 
  6 struct Treap
  7 {
  8     int left,right,val,rnd,size;
  9 }tree[100005];
 10 int n,m,size,root,ans,delta;
 11 
 12 void update(int k)
 13 {
 14     tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+1;
 15 }
 16 
 17 void lturn(int &k)
 18 {
 19     int t=tree[k].right;
 20     tree[k].right=tree[t].left;
 21     tree[t].left=k;
 22     tree[t].size=tree[k].size;
 23     update(k);
 24     k=t;
 25 }
 26 
 27 void rturn(int &k)
 28 {
 29     int t=tree[k].left;
 30     tree[k].left=tree[t].right;
 31     tree[t].right=k;
 32     tree[t].size=tree[k].size;
 33     update(k);
 34     k=t;
 35 }
 36 
 37 void insert(int &k,int x)
 38 {
 39     if(k==0)
 40     {
 41         size++;k=size;
 42         tree[k].size=1;
 43         tree[k].val=x;
 44         tree[k].rnd=rand();
 45         return;
 46     }
 47     tree[k].size++;
 48     if(x>tree[k].val)
 49     {
 50         insert(tree[k].right,x);
 51         if(tree[tree[k].right].rnd<tree[k].rnd) lturn(k);
 52     }
 53     else
 54     {
 55         insert(tree[k].left,x);
 56         if(tree[tree[k].left].rnd<tree[k].rnd) rturn(k);
 57     }
 58 }
 59 
 60 int del(int &k,int x)
 61 {
 62     int t;
 63     if(k==0) return 0;
 64     if(tree[k].val<x)
 65     {
 66         t=tree[tree[k].left].size+1;
 67         k=tree[k].right;
 68         return t+del(k,x);
 69     }
 70     else
 71     {
 72         t=del(tree[k].left,x);
 73         tree[k].size-=t;
 74         return t;
 75     }
 76 }
 77 
 78 int query(int k,int x)
 79 {
 80     if(tree[tree[k].left].size+1==x) return tree[k].val+delta;
 81     else if(tree[tree[k].left].size+1<x) return query(tree[k].right,x-tree[tree[k].left].size-1);
 82     else return query(tree[k].left,x);
 83 }
 84 
 85 int main()
 86 {
 87     scanf("%d%d",&n,&m);
 88     while(n--)
 89     {
 90         char ch[5];
 91         int x;
 92         scanf("%s %d",ch,&x);
 93         switch(ch[0])
 94         {
 95             case ‘I‘:if(x>=m)insert(root,x-delta);break;
 96             case ‘A‘:delta+=x;break;
 97             case ‘S‘:delta-=x;ans+=del(root,m-delta);break;
 98             case ‘F‘:
 99                 if(tree[root].size>=x) printf("%d\n",query(root,tree[root].size-x+1));
100                 else printf("-1\n");
101             break;
102         }
103     }
104     printf("%d\n",ans);
105     return 0;
106 }