一道treap的喜闻乐见的题目

据说这题还能再用Splay AC一次呢

不管了先把treap的模版带上来..

treap我还是记得的只不过delete_node的时候出了点"小小"的问题

导致我WA了2次

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int size;
    int weight;
    int val;
    node * ch[2];
};
node * root;
node * null;
node * new_node(int x)
{
    static node a[100005];
    static int top=0;
    node * t=&a[top++];
    t->size=1;
    t->weight=rand();
    t->val=x;
    t->ch[0]=null;
    t->ch[1]=null;
    return t;
}
void rotate(node * &x,int c)
{
    node * y=x->ch[c];
    x->ch[c]=y->ch[!c];
    y->ch[!c]=x;
    y->size=x->size;
    x->size=x->ch[0]->size+x->ch[1]->size+1;
    x=y;
}
void insert_node(node * &x,node * y)
{
    if (x==null)
    {
        x=y;
        return;
    }
    x->size++;
    int c;
    if (y->val>x->val)
    {
        c=1;
    }
    else
    {
        c=0;
    }
    insert_node(x->ch[c],y);
    if (x->ch[c]->weight>x->weight)
    {
        rotate(x,c);
    }
}
void delete_node(node * &x)
{
    x->size--;
    if (x->ch[0]==null)
    {
        if (x->ch[1]==null)
        {
            x=null;
            return;
        }
        rotate(x,1);
        delete_node(x->ch[0]);
    }
    else
    {
        delete_node(x->ch[0]);
    }
}
int find_kth(node * x,int k)
{
    if (k==x->ch[0]->size+1)
    {
        return x->val;
    }
    else if (k<=x->ch[0]->size)
    {
        return find_kth(x->ch[0],k);
    }
    else
    {
        return find_kth(x->ch[1],k-x->ch[0]->size-1);
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    null=new_node(0);
    null->size=0;
    null->weight=-1;
    null->ch[0]=null;
    null->ch[1]=null;
    root=null;
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    int sum=0;
    int tot=0;
    int ans=0;
    for (i=0;i<n;i++)
    {
        static char a[5];
        scanf("%s",a);
        if (a[0]=='I')
        {
            int x;
            scanf("%d",&x);
            if (x<m) continue;
            x-=sum;
            insert_node(root,new_node(x));
            tot++;
        }
        else if (a[0]=='A')
        {
            int x;
            scanf("%d",&x);
            sum+=x;
        }
        else if (a[0]=='S')
        {
            int x;
            scanf("%d",&x);
            sum-=x;
            for (;;)
            {
                if (tot==0) break;
                if (find_kth(root,1)+sum<m)
                {
                    delete_node(root);
                    tot--;
                    ans++;
                }
                else
                {
                    break;
                }
            }
        }
        else
        {
            int k;
            scanf("%d",&k);
            if (k<=tot)
            {
                printf("%d\n",find_kth(root,tot-k+1)+sum);
            }
            else
            {
                printf("-1\n");
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}