学了Splay，，，练练手

多维护一个size域，就可以求k大值辣

昨晚调到接近3点还是RTE/WA，，cry

今天把每个节点加个cnt域就过了

（出现重复的数字的情况

#include
     
      #include
      
       using namespace std;int m,d,ans;struct Node{    int key,s,cnt;//size    Node *l,*r,*f;//left,right,father};class SplayTree{public:    void Init(){rt=NULL;}    int S(Node *T){
    return (NULL==T)?0:T->s;}    void Zag(Node *x){
    //left rotate        Node *y=x->f;//y is the father of x        y->r = x->l;        if (x->l)x->l->f = y;//if x has left child        x->f =y->f;        if (y->f){
    //y is not root            if (y==y->f->l)y->f->l=x;//y if left child            else y->f->r=x;//y is right child        }        y->f=x;        x->l=y;        y->s=S(y->l)+S(y->r)+y->cnt;        x->s=S(x->l)+S(x->r)+x->cnt;    }    void Zig(Node *x){
    //right rotate        Node *y=x->f;//y is the father of x        y->l = x->r;        if (x->r)x->r->f=y;        x->f = y->f;        if (y->f){            if (y==y->f->l)y->f->l=x;            else y->f->r=x;        }        y->f=x;        x->r=y;        y->s=S(y->l)+S(y->r)+y->cnt;        x->s=S(x->l)+S(x->r)+x->cnt;    }    void Splay(Node *x){        while (x->f){            Node *p=x->f;            if (!p->f){                if (x==p->l)Zig(x);                else Zag(x);            }else if (x==p->l){                if (p==p->f->l){Zig(p);Zig(x);}                else {Zig(x);Zag(x);}            }else {
    //x==p->r                if (p==p->f->r){Zag(p);Zag(x);}                else {Zag(x);Zig(x);}            }        }        rt=x;    }    void Insert(int x){        Node *T=rt,*fa=NULL;        while (T){            fa=T;            T->s++;            if (x==T->key){T->cnt++;Splay(T);return;}            else if (x
       
        key)T=T->l;            else {T=T->r;}        }        T=(Node*)malloc(sizeof(Node));        T->key=x;        T->l=T->r=NULL;        T->f=fa;        T->s=T->cnt=1;        if (fa){            if (fa->key>x)fa->l=T;            else fa->r=T;        }        Splay(T);    }    int Findkth(Node *T,int k){
    //find the K-th biggest number        if (k< S(T->r)+1)return Findkth(T->r,k);        else if (k>S(T->r)+T->cnt)Findkth(T->l,k-S(T->r)-T->cnt);        else {Splay(T);return T->key;}    }    void Goaway(Node *&T,Node *fa){        if (NULL==T)return ;        if (T->key>=m-d){Goaway(T->l,T);}        else {            ans+=S(T->l)+T->cnt;            T=T->r;            if (T)T->f=fa;            if (fa==NULL)rt=T;            Goaway(T,fa);        }        if (T)T->s=T->cnt+S(T->l)+S(T->r);    }    void Work(char ch,int x){        if (ch=='I'&&x>=m)Insert(x-d);        if (ch=='A')d+=x;        if (ch=='S'){d-=x;Goaway(rt,NULL);}        if (ch=='F'){            if (S(rt) < x)puts("-1");            else printf("%d\n",Findkth(rt,x)+d);        }    }private:    Node *rt;//root};int main(){    freopen("fuck.in","r",stdin);    SplayTree T;    T.Init();    int n,x;    char ch;    scanf("%d%d\n",&n,&m);    for (;n--;){        scanf("%c %d\n",&ch,&x);        T.Work(ch,x);    }    printf("%d\n",ans);    return 0;}