思路

平衡树的题目

题目中的全部减少可以通过维护全局的减少量S（不过我使用了打tag的方式），然后每次插入的时候插入\(v_i-S\)，删除的时候直接在平衡树上二分移除对应的子树即可

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int Nodecnt=0,root,n,lim;struct Node{    int lson,rson,sz,val,ran,add,times;}Treap[100100*2];queue
        
          q;void throwin(int x){    q.push(x);}int getnew(int val){    int o;    if(q.size())        o=q.front(),q.pop();    else        o=++Nodecnt;    Treap[o].lson=Treap[o].rson=0;    Treap[o].sz=Treap[o].times=1;    Treap[o].ran=rand();    Treap[o].val=val;    Treap[o].add=0;    return o;}void pushup(int o){    Treap[o].sz=Treap[Treap[o].lson].sz+Treap[Treap[o].rson].sz+Treap[o].times;}void pushdown(int o){    if(Treap[o].add){        Treap[Treap[o].lson].val+=Treap[o].add;        Treap[Treap[o].rson].val+=Treap[o].add;        Treap[Treap[o].lson].add+=Treap[o].add;        Treap[Treap[o].rson].add+=Treap[o].add;        Treap[o].add=0;    }}void rorateL(int &o){    int x=Treap[o].rson;    pushdown(o);    pushdown(x);    Treap[o].rson=Treap[x].lson;    Treap[x].lson=o;    pushup(o);    pushup(x);    o=x;}void rorateR(int &o){    int x=Treap[o].lson;    pushdown(o);    pushdown(x);    Treap[o].lson=Treap[x].rson;    Treap[x].rson=o;    pushup(o);    pushup(x);    o=x;}void insert(int val,int &o){    if(!o){        o=getnew(val);        return;    }    pushdown(o);    Treap[o].sz++;    if(val
         
          Treap[o].val){ insert(val,Treap[o].rson); if(Treap[Treap[o].rson].ran
          
           val){ del(val,Treap[o].lson); pushup(o); return; }}int query(int val,int o){ if(!o) return -1; pushdown(o); if(val>=Treap[Treap[o].rson].sz+1&&val<=Treap[Treap[o].rson].sz+Treap[o].times) return Treap[o].val; else if(val>Treap[Treap[o].rson].sz+Treap[o].times) return query(val-Treap[Treap[o].rson].sz-Treap[o].times,Treap[o].lson); else return query(val,Treap[o].rson);}int main(){ int cnt=0; scanf("%d %d",&n,&lim); for(int i=1;i<=n;i++){ char c=getchar(); while(c!='I'&&c!='A'&&c!='S'&&c!='F') c=getchar(); if(c=='I'){ int k; scanf("%d",&k); if(k