我用的SBT，事实上所有的BST都可以，但是用STL则无法，STL无法维护第K大。
还可以用线段树（本机房一人），还可以用跳跃表（某省队神牛），比较大众的就是BST。
贴一下我的Code:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,t,deta,num,a;
const int maxn=100000;
int s[maxn+10],x[maxn+10],l[maxn+10],r[maxn+10];
void zag(int &t)
{
int y=l[t];
l[t]=r[y];
r[y]=t;
s[t]=s[l[t]]+s[r[t]]+1;
s[y]=s[l[y]]+s[r[y]]+1;
t=y;
}
void zig(int &t)
{
int y=r[t];
r[t]=l[y];
l[y]=t;
s[t]=s[l[t]]+s[r[t]]+1;
s[y]=s[l[y]]+s[r[y]]+1;
t=y;
}
void maintain(int &t,bool flag)
{
if (!t) return;
if (flag)
{
if (s[l[l[t]]]>s[r[t]]) zag(t);
else if (s[r[l[t]]]>s[r[t]])
{
zig(l[t]); zag(t);
}
else return;
}
else
{
if (s[r[r[t]]]>s[l[t]]) zig(t);
else if (s[l[r[t]]]>s[l[t]])
{
zag(r[t]); zig(t);
}
else return;
}
maintain(l[t],1);
maintain(r[t],0);
maintain(t,1);
maintain(t,0);
}
void insert(int &t,int k)
{
if (!t)
{
x[t=++a]=k;
s[a]=1;
}
else
{
s[t]++;
if (k<=x[t]) insert(l[t],k);
else insert(r[t],k);
maintain(t,k<=x[t]);
}
}
int find(int t,int k)
{
if (k==s[r[t]]+1) return x[t];
if (k<=s[r[t]]) return find(r[t],k);
else return find(l[t],k-s[r[t]]-1);
}
void _delete(int &t)
{
if (!t) return;
if (x[t]+deta>=m)
{
_delete(l[t]);
s[t]=s[l[t]]+s[r[t]]+1;
maintain(t,s[l[t]]>s[r[t]]);
}
else
{
num+=s[l[t]]+1;
t=r[t];
_delete(t);
}
}
int main()
{
freopen("cashier.in","r",stdin);
freopen("cashier.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=0; i<n; i++)
{
char flag=(getchar(),getchar());
int k;
scanf("%d",&k);
switch (flag)
{
case 'I':
if (k>=m) insert(t,k-deta);
break;
case 'A':
deta+=k;
break;
case 'S':
deta-=k;
_delete(t);
break;
case 'F':
if (k>s[t]) printf("%d\n",-1);
else printf("%d\n",find(t,k)+deta);
break;
}
}
printf("%d",num);
fclose(stdin);
fclose(stdout);
return 0;
}