名副其实的调了一下午……
每做一道题都是对我那不规范的Splay代码的刀刻斧凿一般的修正啊……
Splay。如果有一批员工不干了，那就找还能干的薪水最少的员工，把它splay到根，删除它的左子树。
然后其他地方加一下标记乱搞就行，这个标记……跟NOIP蚯蚓那个题很像。qwq。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cstdlib>
#define maxn 1000200
using namespace std; inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} int CNT;
long long ans;
struct Splay{
struct Node{
int sum,size,fa,e[],val;
}tree[maxn];
int point,tot,root;
Splay(){point=tot=root=; }
inline int iden(int x){ return x==tree[tree[x].fa].e[]?:; }
inline void connect(int x,int fa,int how){ tree[x].fa=fa; tree[fa].e[how]=x; }
inline void update(int x){ tree[x].size=tree[tree[x].e[]].size+tree[tree[x].e[]].size+tree[x].sum; }
inline void rotate(int x){
int y=tree[x].fa; int r=tree[y].fa;
if(root==y) root=x;
int sony=iden(x); int sonr=iden(y);
int b=tree[x].e[sony^];
connect(b,y,sony);
connect(y,x,sony^);
connect(x,r,sonr);
update(y); update(x);
}
void splay(int pos,int to){
to=tree[to].fa;
while(tree[pos].fa!=to){
if(tree[tree[pos].fa].fa==to) rotate(pos);
else
if(iden(pos)==iden(tree[pos].fa)){
rotate(tree[pos].fa);
rotate(pos);
}
else{ rotate(pos); rotate(pos); }
}
}
int create(int val,int fa){
tree[++tot].val=val; tree[tot].fa=fa;
tree[tot].sum=tree[tot].size=;
return tot;
}
int build(int val){
if(root==){ root=create(val,); return root; }
int now=root;
while(now){
tree[now].size++;
if(tree[now].val==val){ tree[now].sum++; return now; }
int nxt=val<tree[now].val?:;
if(tree[now].e[nxt]==){
connect(create(val,now),now,nxt);
update(now);
return tot;
}
now=tree[now].e[nxt];
}
return ;
}
inline void insert(int val){
int p=build(val);
if(++CNT==){
CNT=;
splay(p,root);
}
}
inline int find(int val){
int now=root;
while(now){
if(tree[now].val==val) return now;
int nxt=val<tree[now].val?:;
now=tree[now].e[nxt];
}
return ;
}
int upper(int val){
int now=root,ans=root;
while(now){
if(tree[now].val==val) return now;
if(val<tree[now].val){
ans=now;
now=tree[now].e[];
}
else now=tree[now].e[];
}
return ans;
}
void dele(int val){
int deal=upper(val);
if(tree[deal].val<val){
ans+=tree[root].size;
root=;
return;
}
splay(deal,root);
ans+=tree[tree[deal].e[]].size;
tree[tree[deal].e[]].fa=;
tree[deal].e[]=;
update(deal);
}
int arank(int rnk){
int now=root;
while(rnk){
int used=tree[now].size-tree[tree[now].e[]].size;
if(tree[tree[now].e[]].size<rnk&&used>=rnk) return tree[now].val;
if(rnk<=used) now=tree[now].e[];
else{
rnk-=used;
now=tree[now].e[];
}
}
if(++CNT==&&now){
splay(now,root);
CNT=;
}
return tree[now].val;
}
int query(int rnk,long long tag){
if(tree[root].size<rnk) return -;
return arank(tree[root].size-rnk+)+tag;
}
}s;
long long tag=;
int main(){int n=read(),m=read();
for(int i=;i<=n;++i){
char c[];int x;
scanf("%s%d",c,&x);
switch(c[]){
case 'I':
if(x>=m) s.insert(x-tag); break;
case 'A': tag+=x; break;
case 'S':
tag-=x; s.dele(m-tag); break;
case 'F': printf("%d\n",s.query(x,tag)); break;
}
}
printf("%lld\n",ans);
return ;
}