【题解】郁闷的出纳员 (luoguP1486) Splay -boshi

题意：给定一个序列，要求可以插入、删除小于某个值的所有数、所有值同时加上 x、查询当前第 k 大的数。

思路：

首先，我们感觉这是一道 Splay 的裸题，但是看到需要区间加减就懵了。
但是仔细一想不难发现，由于所有的加减操作是对全部数据而言的，所以我们可以建立一个变量保存全部的数相对于 Splay 中的值加减了多少。
至于第 k 大询问，我们可以给每个节点新建一个值：子树大小，以便进行二分。
与以往的 Splay 不同的是，我们的值可能重复，所以需要给每个节点新建一个值：值的个数。这样才可以既满足 Splay 的有序性，又可以方便递归。
所以我们的 Splay 节点的结构差不多就出来了：

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 400000

using namespace std;

typedef struct snode{int x,siz,s[2],f,c;snode(){x=siz=s[0]=s[1]=f=c=0;}}Splay_Node;
typedef struct qret{int x,a;}Q_return;
Splay_Node t[MX];

int root,cnt,bound,n,pls,num,goout;

void update(int a){t[a].siz=t[t[a].s[0]].siz+t[t[a].s[1]].siz+t[a].c;}
bool pos(int a){return t[t[a].f].s[1]==a;}
void rot(int a)
{
    int f=t[a].f,g=t[f].f,p=pos(a),q=pos(f);
    t[f].s[p]=t[a].s[!p],t[a].s[!p]=f,t[f].f=a;
    if(t[f].s[p])t[t[f].s[p]].f=f;
    if(t[a].f=g)t[g].s[q]=a;
    update(a),update(f);
}
void splay(int a)
{
    while(t[a].f)
        if(!t[t[a].f].f)rot(a);
        else if(pos(a)!=pos(t[a].f))rot(a),rot(a);
        else rot(t[a].f),rot(a);
    root=a;
}
void insrt(int x,int fa,int &a)
{
    if(!a)a=++cnt,t[a].x=x,t[a].f=fa,t[a].siz=t[a].c=1,splay(a);
    else if(x==t[a].x){t[a].c++,t[a].siz++;splay(a);}
    else if(x<t[a].x)insrt(x,a,t[a].s[0]);
    else insrt(x,a,t[a].s[1]);
}
Q_return prep(int x,int a)
{
    Q_return ret,p;
    ret.a=a,ret.x=-1e8;
    if(!a)return ret;
    else if(x==t[a].x){ret.x=x;return ret;}
    else if(t[a].x<x)
    {
        ret.x=t[a].x;
        p=prep(x,t[a].s[1]);
        if(p.x>ret.x)return p;
        else return ret;
    }
    else return prep(x,t[a].s[0]);
}
void smax()
{
    int a=root;
    while(t[a].s[1])a=t[a].s[1];
    splay(a);
}
int del()
{
    Q_return ret=prep(bound-pls-1,root);
    if(ret.a==0)return 0;
    splay(ret.a);
    int dsiz=t[t[root].s[0]].siz+t[root].c;
    root=t[root].s[1],t[root].f=0;
    return dsiz;

}
int kth(int k,int a)
{
    int nowl=t[t[a].s[0]].siz+1,nowr=nowl+t[a].c-1;
    if(!a)return -1;
    else if(nowl<=k&&k<=nowr)return t[a].x;
    else if(k<nowl)return kth(k,t[a].s[0]);
    else return kth(k-nowr,t[a].s[1]);
}
int main()
{
    int a,t;char ch;
    scanf("%d%d",&n,&bound);
    for(int i=1;i<=n;i++)
    {
        for(ch=getchar();ch!='I'&&ch!='A'&&ch!='S'&&ch!='F';ch=getchar());
        scanf("%d",&a);
        if(ch=='I'&&a>=bound){insrt(a-pls,0,root),num++;}
        else if(ch=='A'){pls+=a;}
        else if(ch=='S'){pls-=a,t=del(),num-=t,goout+=t;}
        else if(ch=='F'){t=kth(num-a+1,root);printf("%d\n",(t==-1?-1:t+pls));}
    }
    printf("%d\n",goout);
    return 0;
}