[BZOJ1503] [NOI2004]郁闷的出纳员

本文主要是介绍[BZOJ1503] [NOI2004]郁闷的出纳员，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1503

题目大意

给定m,支持
I x:插入x(若x< m则不插入)
S x:对全体权值-x,若更新后的权值小于m则踢出
A x:对全体权值+x
F x:查询第k大
最后输出踢出的人数(不包括插入时小于m的)

题解

平衡树模板题

constmaxn=300005;
varw:array[-1..maxn,1..7]of longint;i,j,k:longint;n,m,sum,a,root,tail:longint;cha:char;
procedure rotate(a,kind:longint);
var b,unkind:longint;
beginunkind:=kind xor 3; b:=w[a,3];w[a,4]:=w[b,4]; dec(w[b,4],w[a,5]+w[w[a,kind],4]);w[w[a,unkind],3]:=b; w[b,kind]:=w[a,unkind];w[a,3]:=w[b,3]; w[a,unkind]:=b;w[b,3]:=a;if w[a,3]<>-1thenif w[w[a,3],1]=bthen w[w[a,3],1]:=aelse w[w[a,3],2]:=a;
end;procedure splay(a,goal:longint);
var b,kind,unkind:longint;
beginwhile w[a,3]<>goal dobeginif w[w[a,3],1]=a then kind:=1 else kind:=2;unkind:=kind xor 3; b:=w[a,3];if w[b,3]=goal then rotate(a,kind)elseif w[w[b,3],kind]=bthen begin rotate(b,kind); rotate(a,kind); endelse begin rotate(a,kind); rotate(a,unkind); end;end;if goal=-1 then root:=a;
end;procedure pushdown(a:longint);
beginif (w[a,6]<>1000000007)and(w[a,6]<>-1000000007) then inc(w[a,6],w[a,7]);if w[a,1]<>-1 then inc(w[w[a,1],7],w[a,7]);if w[a,2]<>-1 then inc(w[w[a,2],7],w[a,7]);w[a,7]:=0;
end;procedure init(a:longint);
var tt,fa,kind:longint;
begintt:=root;while tt<>-1 dobeginif w[tt,7]<>0 then pushdown(tt);inc(w[tt,4]); fa:=tt;if w[tt,6]=a then break;if a<w[tt,6]then begin tt:=w[tt,1]; kind:=1; endelse begin tt:=w[tt,2]; kind:=2; end;end;if tt<>-1then begin inc(w[tt,5]); splay(tt,-1); endelse begin inc(tail); w[tail,1]:=-1; w[tail,2]:=-1; w[tail,3]:=fa; w[tail,4]:=1; w[tail,5]:=1; w[tail,6]:=a; w[tail,7]:=0; w[fa,kind]:=tail; splay(tail,-:span class="hljs-number">1); end;
end;function getkth(k:longint):longint;
var tt:longint;
begintt:=root;while (k<=w[w[tt,1],4])or(k>=w[w[tt,1],4]+w[tt,5]+1) dobeginif w[tt,7]<>0 then pushdown(tt);if k<=w[w[tt,1],4]then tt:=w[tt,1]else begin k:=k-w[w[tt,1],4]-w[tt,5]; tt:=w[tt,2]; end;end;pushdown(tt);exit(w[tt,6]);
end;beginreadln(n,m); sum:=0; root:=2; tail:=2;w[1,1]:=-1; w[1,2]:=-1; w[1,3]:=2; w[1,4]:=1; w[1,5]:=1; w[1,6]:=-1000000007; w[1,7]:=0;w[2,1]:=1; w[2,2]:=-1; w[2,3]:=-1; w[2,4]:=2; w[2,5]:=1; w[2,6]:=1000000007; w[2,7]:=0;for i:=1 to n dobeginreadln(cha,a);case cha of'I':begin if a>=m then init(a); end;'A':begin inc(w[root,7],a); end;'S':begin inc(w[root,7],-a); init(m); inc(sum,w[w[root,1],4]-1);if w[root,5]=1then begin root:=w[root,2]; w[root,3]:=-1; init(-1000000007); endelse begin w[root,4]:=w[w[root,2],4]+w[root,5]-1; dec(w[root,5]); w[root,1]:=-1; init(-1000000007); end;end;'F':begin if w[root,4]-2<a then writeln(-1)else writeln(getkth(w[root,4]-a));end;end;end;writeln(sum);
end.