题意：插入一个数，全体加，全体减，删除小于一个数的所有数，求$k$大

---

 

全局标记然后平衡树直接搞就行了

删除操作不断的找最小值然后删除复杂度是对的，然而$Candy?$这个沙茶找最小没有判$x==0$超时郁闷了好长时间....

或者你也可以乱搞一个$treap$的左子树删除...时间差了$50ms$左右

然后对于第一种做法潸然生日再次自带$50ms$常数

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define lc t[x].l#define rc t[x].rconst int N=1e5+5;int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,lim,all,v;char s[5];struct Node{    int l,r,v,w,size,rnd;}t[N];int sz,root;inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;}inline void rturn(int &x){    int c=lc;lc=t[c].r;t[c].r=x;    t[c].size=t[x].size;update(x);x=c;}inline void lturn(int &x){    int c=rc;rc=t[c].l;t[c].l=x;    t[c].size=t[x].size;update(x);x=c;}void treIns(int &x,int v){    if(x==0){        x=++sz;        t[x].l=t[x].r=0;t[x].v=v;        t[x].w=t[x].size=1;        t[x].rnd=rand();    }else{        t[x].size++;        if(v==t[x].v) t[x].w++;        else if(v
          
           1) t[x].w--,t[x].size--; else if(!lc||!rc) x=lc|rc; else if(t[lc].rnd
           
            =lim) treIns(root,v-all);} else if(s[0]=='A') all+=v; else if(s[0]=='S'){ all-=v; //int mn=findMin(root);//printf("mn %d\n",mn); //while(mn+all
            
             t[root].size) puts("-1"); else printf("%d\n",kth(root,t[root].size-v+1)+all); } } printf("%d",delcnt);}