[NOI2004]郁闷的出纳员（到底是谁郁闷啊？）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

一道 FHQ treap 的裸水题，卡了这么久。（咦~一看就是修为不够）

题解什么的，不用看的（话说那我为什么要写这篇题解咧...），直接 FHQ 模板腾上去就能秒 A 了（打脸）

谈谈 debug ... 首先是一个 0 写成了 1 ，GG ，然后是 m-1 出现了乱七八糟的东西，然后又被误导在 insert 操作不执行时 ++res ... 等，以上

（咦~这个人一看就是菜鸡这么裸的题都要 debug 这么久）(*/ω＼*)

所以就是要套 FHQ 里面的merge 、split_key、split_val、get_rank、ins （以及一些update 、pushdown、rand 什么零碎操作）

如果你还不是很了解 FHQ treap ，可以看这里

然后这题的增减工资其实可以打一下懒标记的啦~（一开始没搞清楚状况没用懒标记直接对 m 进行操作，后来发现这个增减工资只对操作前存在的员工有用啊！），

split 的时候 pushdown 一下就好了（merge 是不用的，因为这里没有直接merge的操作，都是先split完了之后才merge的）

所以...上代码...

//by Judge
#include<iostream>
#include<cstdio>
using namespace std;
const int M=2e5+;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
}
inline int cread(){
char c=getchar();
while(!isupper(c)) c=getchar();
switch(c){
case 'I': return ;
case 'A': return ;
case 'S': return ;
case 'F': return ;
}
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(int x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
int n,m,q,res,cnt,root;
struct Node { int val,key,siz,tag,ch[]; } t[M];
inline int Rand() { static int seed=; return seed=int(seed*48271LL%(~0u>>)); }
inline void update(int now){ t[now].siz=t[t[now].ch[]].siz+t[t[now].ch[]].siz+; }
inline void pushdown(int now){ //多了pushdown
t[t[now].ch[]].val+=t[now].tag,t[t[now].ch[]].val+=t[now].tag,
t[t[now].ch[]].tag+=t[now].tag,t[t[now].ch[]].tag+=t[now].tag,t[now].tag=;
}
int merge(int u,int v) {
if(!u || !v) return u|v;
if(t[u].key<t[v].key) { t[u].ch[]=merge(t[u].ch[],v),update(u); return u; }
else { t[v].ch[]=merge(u,t[v].ch[]),update(v); return v; }
}
void split_val(int now,int k,int& x,int& y) {
if(!now) return (void)(x=y=); pushdown(now);
if(t[now].val<=k) split_val(t[x=now].ch[],k,t[now].ch[],y);
else split_val(t[y=now].ch[],k,x,t[now].ch[]); update(now);
}
void split_k(int now,int k,int& x,int& y) {
if(!now) return (void)(x=y=); pushdown(now);
if(t[t[now].ch[]].siz>=k) split_k(t[y=now].ch[],k,x,t[now].ch[]),update(now);
else split_k(t[x=now].ch[],k-t[t[now].ch[]].siz-,t[now].ch[],y),update(now);
}
inline void ins(int x) { int u,a,b; t[u=++cnt].key=Rand(),t[u].val=x,t[u].siz=,split_val(root,x,a,b),root=merge(merge(a,u),b); }
inline int get_val(int x) { int a,b,c,d,e; split_k(root,x-,a,b),split_k(b,,c,d),e=t[c].val,root=merge(a,merge(c,d)); return e; }
signed main() {
n=read(),m=read()-;
for(int opt,x;n;--n){
opt=cread(),x=read();
switch(opt){ //四个较为常规的操作
case : if(x>m) ins(x); break;
case : t[root].val+=x,t[root].tag+=x; break;
case : t[root].val-=x,t[root].tag-=x,split_val(root,m,x,root),res+=t[x].siz; break;
case : print(x>t[root].siz?-:get_val(t[root].siz-x+)); break;
} Ot();
} print(res),Ot(); return ;
}