平衡树之伸展树（Splay Tree）题目整理

前言

前言

学习于yyb
本来是想写个算法解释，克自己写了一半总感觉像复制的，各位就去yyb哪里学吧
这里附上几个BZOJ的模板题
\n
\n
\n
\n

练习1 BZOJ 3224 普通平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作

插入 \(x\) 数

删除 \(x\) 数(若有多个相同的数，因只删除一个)

查询 \(x\) 数的排名(排名定义为比当前数小的数的个数 \(+1\) 。若有多个相同的数，因输出最小的排名)

查询排名为 \(x\) 的数

求 \(x\) 的前驱(前驱定义为小于 \(x\) ，且最大的数)

求 \(x\) 的后继(后继定义为大于 \(x\) ，且最小的数)

splay的模板题
也就是splay的全部操作
前言的博客讲的很详尽了

/**************************************************************
    Problem: 3224
    User: 3010651817
    Language: C++
    Result: Accepted
    Time:500 ms
    Memory:10672 kb
****************************************************************/
 
#include <cstdio>
#include <iostream>
#define maxN 400007
using namespace std;
inline int read() {
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9') {if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
int root,tot; 
struct Node {
    int ch[2],val,ff,size,cnt;
}t[maxN];
inline void pushup(int u) {
    t[u].size=t[t[u].ch[0]].size+t[t[u].ch[1]].size+t[u].cnt;
}
inline void rotate(int x) { //核心操作->旋转 
    int y=t[x].ff,z=t[y].ff,k=(t[y].ch[1]==x);
    t[z].ch[t[z].ch[1]==y]=x;//爷爷和儿子 
    t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];//爸爸和孙子
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;
    t[y].ff=x;//爸爸和儿子 
    pushup(y); 
    pushup(x);
}
 
inline void splay(int x,int goal) {
    while(t[x].ff!=goal) {
        int y=t[x].ff,z=t[y].ff;
        if(z!=goal)
            (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(!goal) root=x;
}
void find(int x) {
    int u=root;
    if(!u) return;
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}
inline void insert(int x) { 
    int u=root,ff=0;
    while(u&&t[u].val!=x) {
        ff=u;
        u=t[u].ch[x>t[u].val];
    }
    if(u)t[u].cnt++;
    else {
        u=++tot;
        if(ff)
            t[ff].ch[x>t[ff].val]=u;
        t[u].ch[0]=t[u].ch[1]=0;
        t[tot].ff=ff;
        t[tot].val=x;
        t[tot].cnt=1;
        t[tot].size=1;
    }
    splay(u,0);
}
int Next(int x,int f) {
    find(x);
    int u=root;
    if(t[u].val>x&&f) return u;
    if(t[u].val<x&&!f) return u;
    u=t[u].ch[f];
    while(t[u].ch[f^1])u=t[u].ch[f^1];
    return u;
}
void Delete(int x) {
    int last=Next(x,0);
    int nxt=Next(x,1);
    splay(last,0);
    splay(nxt,last);
    int del=t[nxt].ch[0];
    if(t[del].cnt>1) t[del].cnt--,splay(del,0);
    else t[nxt].ch[0]=0;
}
int k_th(int x) {
    int u=root;
    if(t[u].size<x) return 0;
    while(1) {
        int y=t[u].ch[0];
        if(x>t[y].size+t[u].cnt) {
            x-=t[y].size+t[u].cnt;
            u=t[u].ch[1];
        } else {
            if(t[y].size>=x) 
                u=y;
            else
                return t[u].val;        
        }
    }
}
int main()
{
    int n=read();
    insert(0x7fffffff);
    insert(-0x7fffffff);
    while(n--)
    {
        int opt=read(),x=read();
        if(opt==1) insert(x);else
        if(opt==2) Delete(x);else
        if(opt==3) find(x),printf("%d\n",t[t[root].ch[0]].size);else
        if(opt==4) printf("%d\n",k_th(x+1));else
        if(opt==5) printf("%d\n",t[Next(x,0)].val);else
        if(opt==6) printf("%d\n",t[Next(x,1)].val);
    }
    return 0;
}

练习2 BZOJ 3223 文艺平衡树

维护一个要m次区间翻转的区间，最后输出
看题目一开始我还以为这是比普通的平衡树厉害的题目，但其实比普通的还简单的一个题
区间翻转，只要范围内的左右节点全部互换就可以了
这就可以类似于线段树的懒惰标记(原来splay也可以pushdown啊)
建树的话，由于区间大小不变
懒得直接套insert
也可以写个build

/**************************************************************
    Problem: 3223
    User: 3010651817
    Language: C++
    Result: Accepted
    Time:2288 ms
    Memory:14968 kb
****************************************************************/
 
#include <cstdio>
#include <iostream>
#define maxN 500007
using namespace std;
inline int read() {
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9') {if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
int root,tot; 
struct Node {
    int ch[2],val,ff,size,cnt;
    int lazy;
}t[maxN];
inline void pushup(int u) {
    t[u].size=t[t[u].ch[0]].size+t[t[u].ch[1]].size+1;
}
void pushdown(int x)
{
    if(t[x].lazy)
    {
        t[t[x].ch[0]].lazy^=1;
        t[t[x].ch[1]].lazy^=1;
        t[x].lazy=0;
        swap(t[x].ch[0],t[x].ch[1]);
    }
}
inline void rotate(int x) { //核心操作->旋转 
    int y=t[x].ff,z=t[y].ff,k=(t[y].ch[1]==x);
    t[z].ch[t[z].ch[1]==y]=x;//爷爷和儿子 
    t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];//爸爸和孙子
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;
    t[y].ff=x;//爸爸和儿子 
    pushup(x);
    pushup(y); 
}
 
inline void splay(int x,int goal) {
    while(t[x].ff!=goal) {
        int y=t[x].ff,z=t[y].ff;
        if(z!=goal)
            (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(!goal) root=x;
}
inline void insert(int x) { 
    int u=root,ff=0;
    while(u&&t[u].val!=x) {
        ff=u;
        u=t[u].ch[x>t[u].val];
    }
        u=++tot;
        if(ff)
            t[ff].ch[x>t[ff].val]=u;
        t[u].ch[0]=t[u].ch[1]=0;
        t[tot].ff=ff;
        t[tot].val=x;
        t[tot].cnt=1;
        t[tot].size=1;
    splay(u,0);
}
int k_th(int x) {
    int u=root;
    while(1) {
        pushdown(u);
        int y=t[u].ch[0];
        if(x>t[y].size+t[u].cnt) {
            x-=t[y].size+t[u].cnt;
            u=t[u].ch[1];
        } else {
            if(t[y].size>=x) 
                u=y;
            else
                return t[u].val;        
        }
    }
}
int n;
inline void write(int x)
{
    pushdown(x);
    if(t[x].ch[0])write(t[x].ch[0]);
    if(t[x].val>1&&t[x].val<n+2)printf("%d ",t[x].val-1);
    if(t[x].ch[1])write(t[x].ch[1]);
}        
void work(int x,int y)
{
    int l=k_th(x);
    int r=k_th(y+2);
    splay(l,0);
    splay(r,l);
    t[t[t[root].ch[1]].ch[0]].lazy^=1;
}
int main()
{
    n=read();
    int m=read();
    for(int i=1;i<=n+2;++i) insert(i);
    while(m--)
    {
        int x=read(),y=read();
        work(x,y);  
    }
    write(root);
    puts("");
    return 0;
}

练习3 BZOJ 1588 [HNOI2002]营业额统计

求\(\sum_{1}^{n}\)最小波动值
最小波动值=min{|该天以前某一天的营业额-该天营业额|}。
很明显，最小波动值就是|该天营业额-他的前驱(<=)|
或者|该天营业额-他的后继(>=)|
两者取min就可以

/**************************************************************
    Problem: 1588
    User: 3010651817
    Language: C++
    Result: Accepted
    Time:232 ms
    Memory:5048 kb
****************************************************************/
 
#include <cstdio>
#include <iostream>
#define maxN 160007
using namespace std;
inline int read() {
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9') {if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f;
}
inline int abs(int a) {
    return a>0 ? a : -a;
}
int root,tot; 
struct Node {
    int ch[2],val,ff,size,cnt;
}t[maxN];
inline void pushup(int u) {
    t[u].size=t[t[u].ch[0]].size+t[t[u].ch[1]].size+t[u].cnt;
}
inline void rotate(int x) { //核心操作->旋转 
    int y=t[x].ff,z=t[y].ff,k=(t[y].ch[1]==x);
    t[z].ch[t[z].ch[1]==y]=x;//爷爷和儿子 
    t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];//爸爸和孙子
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;
    t[y].ff=x;//爸爸和儿子 
    pushup(x);
    pushup(y); 
}
 
inline void splay(int x,int goal) {
    while(t[x].ff!=goal) {
        int y=t[x].ff,z=t[y].ff;
        if(z!=goal)
            (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(!goal) root=x;
}
void find(int x) {
    int u=root;
    if(!u) return;
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}
inline void insert(int x) { 
    int u=root,ff=0;
    while(u&&t[u].val!=x) {
        ff=u;
        u=t[u].ch[x>t[u].val];
    }
    if(u)t[u].cnt++;
    else {
        u=++tot;
        if(ff)
            t[ff].ch[x>t[ff].val]=u;
        t[u].ch[0]=t[u].ch[1]=0;
        t[tot].ff=ff;
        t[tot].val=x;
        t[tot].cnt=1;
        t[tot].size=1;
    }
    splay(u,0);
}
int Next(int x,int f) {
    int u=root;
     
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    if(x==t[u].val) return u;
    splay(u,0);
    u=root;
    if(t[u].val>x&&f) return u;
    if(t[u].val<x&&!f) return u;
    u=t[u].ch[f];
    while(t[u].ch[f^1])u=t[u].ch[f^1];
    return u;
}
int main()
{
    //freopen("a.in","r",stdin);
    int n=read();
    insert(0x7fffffff);
    insert(-0x7fffffff);
    int tot=0;
    int x=read();
    int dsr=x;
    insert(x);
    tot+=x;
    x=read();
    insert(x);
    tot+=abs(x-dsr);
    for(int i=3;i<=n;++i)
    {
        x=read();
        int tmp1=t[Next(x,0)].val;
        int tmp2=t[Next(x,1)].val;
        insert(x);
        int ans=0x3f3f3f3f;
        if(tmp1!=-0x7fffffff)
            ans=min(ans,abs(tmp1-x));
        if(tmp2!=0x7fffffff)
            ans=min(ans,abs(tmp2-x));
        tot+=ans;
        //cout<<ans<<"\n";
    }
    printf("%d",tot);
    return 0;
}

练习4 BZOJ 1208 [HNOI2004]宠物收养场

题目
一开始读错了题(郝志章)
很明显，题目想让你建两棵splay(s)，但是
如果一开始宠物多，领养者少，过渡到到宠物少，领养者多的情况的时候，一定会出现树上为空的情况，所以我们就只是用一颗树就可以了

/**************************************************************
    Problem: 1208
    User: 3010651817
    Language: C++
    Result: Accepted
    Time:208 ms
    Memory:8800 kb
****************************************************************/
 
#include <cstdio>
#include <iostream>
#define mod 1000000
#define inf 0x7fffffff
#define maxN 320007
using namespace std;
int n;
int tot_pet,tot_adopter;
inline int min(int a,int b) {
    return a>b?b:a;
}
inline int abs(int a) {
    return a>0?a:-a;
}
inline int read() {
    int x=0,f=1;
    char s=getchar();
    while(s<'0'||s>'9') {
        if(s=='-')f=-1;
        s=getchar();
    }
    while('0'<=s&&s<='9') {
        x=x*10+s-'0';
        s=getchar();
    }
    return x*f;
}
int root,tot;
struct Node {
    int ch[2],val,ff,size,cnt;
} t[maxN];
inline void pushup(int u) {
    t[u].size=t[t[u].ch[0]].size+t[t[u].ch[1]].size+t[u].cnt;
}
inline void rotate(int x) {
    int y=t[x].ff,z=t[y].ff,k=(t[y].ch[1]==x);
    t[z].ch[t[z].ch[1]==y]=x;
    t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;
    t[y].ff=x;
    pushup(x);
    pushup(y);
}
inline void splay(int x,int goal) {
    while(t[x].ff!=goal) {
        int y=t[x].ff,z=t[y].ff;
        if(z!=goal)
            (t[y].ch[0]==x)^(t[z].ch[0]==y)?rotate(x):rotate(y);
        rotate(x);
    }
    if(!goal) root=x;
}
void find(int x) {
    int u=root;
    if(!u) return;
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}
inline void insert(int x) {
    int u=root,ff=0;
    while(u&&t[u].val!=x) {
        ff=u;
        u=t[u].ch[x>t[u].val];
    }
    if(u)t[u].cnt++;
    else {
        u=++tot;
        if(ff)
            t[ff].ch[x>t[ff].val]=u;
        t[u].ch[0]=t[u].ch[1]=0;
        t[tot].ff=ff;
        t[tot].val=x;
        t[tot].cnt=1;
        t[tot].size=1;
    }
    splay(u,0);
}
int Next(int x,int f) {
    find(x);
    int u=root;
    if(t[u].val>x&&f) return u;
    if(t[u].val<x&&!f) return u;
    u=t[u].ch[f];
    while(t[u].ch[f^1])u=t[u].ch[f^1];
    return u;
}
void Delete(int x) {
    int last=Next(x,0);
    int nxt=Next(x,1);
    splay(last,0);
    splay(nxt,last);
    int del=t[nxt].ch[0];
    if(t[del].cnt>1) t[del].cnt--,splay(del,0);
    else t[nxt].ch[0]=0;
}
inline int check(int x) {
    int u=root;
    if(!u) return -1;
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    if(x==t[u].val) return u;
    return -1;
}
//维护一颗splay就可以
//如果一开始宠物多，人少，之后如果宠物少，人多的话 ，splay树必须先为空
//这样就可以重复利用了
int main() {
 
    n=read();
    insert(inf);
    insert(-inf);
    int tot=0;
    while(n--) {
        int a=read(),b=read();
        if(a) { //adopter
            if(tot_pet) { //还有宠物
                tot_pet--;
                int zz=check(b);
                if(zz!=-1) {
                    Delete(t[zz].val);
                    continue;
                }//检查一下有没有前面等于自己的宠物
                int ans=inf;
                int tmp1=Next(b,0);//前驱，注意是标号！！！
                int tmp2=Next(b,1);//后继
                //cout<<t[tmp1].val<<" "<<t[tmp2].val<<"\n";
                if(t[tmp1].val==-inf) {//没有前驱
                    tot+=abs(b-t[tmp2].val);
                    tot%=mod;
                    Delete(t[tmp2].val);
                    //continue;
                } else if(t[tmp2].val==inf) { //没有后缀
                    tot+=abs(b-t[tmp1].val);
                    tot%=mod;
                    Delete(t[tmp1].val);
                    //continue;
                } else if(abs(b-t[tmp1].val) > abs(b-t[tmp2].val)) {
                    tot+=abs(b-t[tmp2].val);
                    tot%=mod;
                    Delete(t[tmp2].val);
                } else {
                    tot+=abs(b-t[tmp1].val);
                    tot%=mod;
                    Delete(t[tmp1].val);
                }
            } else {
                insert(b);
                tot_adopter++;
            }
        } else { //pet
            if(tot_adopter) { //还有领养者
                tot_adopter--;
                int zz=check(b);
                if(zz!=-1) {
                    Delete(t[zz].val);
                    continue;
                }//检查一下有没有前面等于自己的宠物
                int ans=inf;
                int tmp1=Next(b,0);//前驱，注意是标号！！！
                int tmp2=Next(b,1);//后继
                //cout<<t[tmp1].val<<" "<<t[tmp2].val<<"\n";
                if(t[tmp1].val==-inf) {//没有前驱
                    tot+=abs(b-t[tmp2].val);
                    tot%=mod;
                    Delete(t[tmp2].val);
                    continue;
                }
                if(t[tmp2].val==inf) {//没有后缀
                    tot+=abs(b-t[tmp1].val);
                    tot%=mod;
                    Delete(t[tmp1].val);
                    continue;
                }
                if(abs(b-t[tmp1].val) > abs(b-t[tmp2].val)) {
                    tot+=abs(b-t[tmp2].val);
                    tot%=mod;
                    Delete(t[tmp2].val);
                } else {
                    tot+=abs(b-t[tmp1].val);
                    tot%=mod;
                    Delete(t[tmp1].val);
                }
            } else { //adopter空了
                insert(b);
                tot_pet++;
            }
        }
    }
    printf("%d\n",tot);
    return 0;
}

练习5 BZOJ 1507 [NOI2003]文本编辑器 editor

题目
注意:luogu的朋友，输入需要注意\r
输出的话，把l到r的子树旋到root右儿子的左儿子上，然后中序遍历
删除l到r的子树的子树，旋转和输出类似
感兴趣的朋友还可以看看
BZOJ 1269（非重题） [AHOI2006]文本编辑器editor
这个

/**************************************************************
    Problem: 1507
    User: 3010651817
    Language: C++
    Result: Accepted
    Time:2128 ms
    Memory:54028 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#define maxn 3000001
using namespace std;
int read()
{
    int x=0,f=1;char s=getchar();
    while('0'>s||s>'9'){
        if(s=='-')f=-1;
        s=getchar();
    }
    while('0'<=s&&s<='9') {
        x=x*10+s-'0';
        s=getchar();
    }
    return x*f;
}
int n,cnt,root,mouse;
int fa[maxn],ch[maxn][2],siz[maxn];
char w[maxn];
void update(int x) {
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
int get(int x) {
    return ch[fa[x]][1]==x;
}
void rotate(int x) {
    int f=fa[x],ff=fa[f],son=get(x);
    ch[f][son]=ch[x][son^1];
    if(ch[f][son]) fa[ch[f][son]]=f;
    fa[f]=x;
    ch[x][son^1]=f;
    fa[x]=ff;
    if(ff) ch[ff][ch[ff][1]==f]=x;
    update(f);
    update(x);
}
void splay(int x,int to) {
    if(x==to||fa[x]==to) return;
    if(to==0) root=x;
    for(int f; (f=fa[x])&&(f!=to); rotate(x)) {
        if(fa[f]!=to)
            rotate(get(x)==get(f)?f:x);
    }
    update(x);
}
int rank(int x,int pos) {
    if(siz[ch[pos][0]]+1==x) {
        splay(pos,0);
        return pos;
    }
    if(siz[ch[pos][0]]>=x) return rank(x,ch[pos][0]);
    else return rank(x-siz[ch[pos][0]]-1,ch[pos][1]);
}
char s[maxn];
int build(int l,int r,int f) {
    if(l>r) return 0;
    int mid=(l+r)>>1,cur=++cnt;
    fa[cur]=f;
    w[cur]=s[mid];
    ch[cur][0]=build(l,mid-1,cur);
    ch[cur][1]=build(mid+1,r,cur);
    update(cur);
    return cur;
}
void insert(int l,int len) {
    int x=rank(l,root),y=rank(l+1,root);
    splay(x,0);
    splay(y,root);
    ch[y][0]=build(1,len,y);
    update(y);
    update(x);
}
void del(int l,int r) {
    int x=rank(l,root),y=rank(r+2,root);
    splay(x,0);
    splay(y,root);
    ch[y][0]=0;
    update(y);
    update(x);
}
void dfs(int x) {
    if(!x) return ;
    dfs(ch[x][0]);
    printf("%c",w[x]);
    dfs(ch[x][1]);
}
void print(int l,int len) {
    int x=rank(l,root),y=rank(l+len+1,root);
    splay(x,0);
    splay(y,root);
    dfs(ch[y][0]);
    puts("");
}
int main() {
    int i,j,t1;
    char op[10];
    char c;
    n=read();
     
    root=++cnt;
    w[cnt]=0;
    siz[cnt]=2;
    ch[cnt][1]=cnt+1;
    cnt++;
    fa[cnt]=cnt-1;
    w[cnt]=0;
    siz[cnt]=1;
    mouse=1;
    for(i=1; i<=n; i++) {
        scanf("%s",op);
        if(op[0]=='I') {
            t1=read();
            for(j=1; j<=t1; j++) {
                c=getchar();
                while(c=='\n'||c=='\r') c=getchar();//超级大坑
                s[j]=c;
            }
            insert(mouse,t1);
        }
        if(op[0]=='D') {
            t1=read();
            del(mouse,mouse+t1-1);
        }
        if(op[0]=='G') {
            t1=read();
            print(mouse,t1);
        }
        if(op[0]=='M') {
            t1=read();
            mouse=t1+1;
        }
        if(op[0]=='N') mouse++;
        if(op[0]=='P') mouse--;
    }
}

练习6 BZOJ 1503 [NOI2004]郁闷的出纳员

题目
由于是全体降工资，涨工资，所以不用lazy，不用改树
直接把标准改一下就,但加入新人的时候，也需要把它的工资改一下。
（标准都改，新人也需要同步）
然后降工资的时候删除一下标准的1到标准前缀的子树就可以了
这里查询第k多工资，而不是第k小，所以需要员工总数-k+1

/**************************************************************
    Problem: 1503
    User: 3010651817
    Language: C++
    Result: Accepted
    Time:784 ms
    Memory:3872 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#define INF 0x3f3f3f3f
#define maxn 110000
using namespace std;
int n,root;
struct Node {
    int ch[2];
    int val;
    int ff;
    int cnt;
    int size;
} t[maxn];
int tot,mm,ans,add;
inline void pushup(int x) {
    t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
inline void rotate(int x) {
    int y=t[x].ff,z=t[y].ff,k=(x==t[y].ch[1]);
    t[z].ch[y==t[z].ch[1]]=x;
    t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;
    t[y].ff=x;
    pushup(y);
    pushup(x);
}
inline void splay(int x,int goal) {
    while(t[x].ff!=goal) {
        int y=t[x].ff;
        int z=t[y].ff;
        if(z!=goal)
            (t[z].ch[0]==y)^(t[y].ch[0]==x)? rotate(x):rotate(y);
        rotate(x);
    }
    if(!goal) root=x;
}
void find(int x) {
    int u=root;
    if(!u) return;
    while(t[u].ch[x>t[u].val]&&x!=t[u].val)
        u=t[u].ch[x>t[u].val];
    splay(u,0);
}
inline void insert(int x) {
    int u=root,ff=0;
    while(u&&t[u].val!=x) {
        ff=u;
        u=t[u].ch[x>t[u].val];
    }
    if(u)t[u].cnt++;
    else {
        u=++tot;
        if(ff)
            t[ff].ch[x>t[ff].val]=u;
        t[u].ch[0]=t[u].ch[1]=0;
        t[tot].ff=ff;
        t[tot].val=x;
        t[tot].cnt=1;
        t[tot].size=1;
    }
    splay(u,0);
}
inline int Next(int x,int f) {
    find(x);
    int u=root;
    if(t[u].val>=x&&f)return u;
    if(t[u].val<=x&&!f)return u;
    u=t[u].ch[f];
    while(t[u].ch[f^1])u=t[u].ch[f^1];
    return u;
}
 
int k_th(int x) {
    int u=root;
    if(t[u].size<x||x<1) return -INF;
    while(1) {
        int y=t[u].ch[0];
        if(x>t[y].size+t[u].cnt) {
            x-=t[y].size+t[u].cnt;
            u=t[u].ch[1];
        } else {
            if(t[y].size>=x)
                u=y;
            else
                return t[u].val;
        }
    }
}
 
int main() {
    insert(+INF);
    scanf("%d%d",&n,&mm);
    int peo=0;
    while(n--) {
        int x;
        char ch[3];
        scanf("%s%d",ch,&x);
        if(ch[0]=='I') {
            if(x>=mm) {
                insert(x-add);
                peo++;
            }
        }
        if(ch[0]=='A')
            add+=x;
        if(ch[0]=='S') {
            add-=x;
            int gg=Next(mm-add,1);
            splay(gg,0);
            ans+=t[t[root].ch[0]].size;
            peo-=t[t[root].ch[0]].size;
            t[t[root].ch[0]].size=t[t[root].ch[0]].cnt=0;
            t[root].ch[0]=0;
            t[0].size=0;
            pushup(root);
        }
        if(ch[0]=='F') {
            int gg=k_th(peo-x+1);
            printf("%d\n",gg==-INF?-1:(gg+add));
        }
    }
    printf("%d\n",ans);
    return 0;
}
/*
思路一样，可惜自己D了2小时没弄出来╮(╯_╰)╭太弱了 
*/