splay

struct splay_tree{
    static const int maxn=2e6+10;
    int ch[maxn][2],fa[maxn];
    int miv[maxn],val[maxn],add[maxn],rev[maxn],siz[maxn];
    int rub[maxn],rub_;//回收池
    int rt,tot;
    //数据结束

    void pushup(int h){//维持，回溯
        int l=ch[h][0],r=ch[h][1];
        miv[h]=val[h];
        if(l)miv[h]=min(miv[h],miv[l]);
        if(r)miv[h]=min(miv[h],miv[r]);
        siz[h]=siz[l]+siz[r]+1;
    }

    void pushdown(int h){//下放懒惰标记
        int l=ch[h][0],r=ch[h][1];
        if(add[h]){
            add[l]+=add[h];val[l]+=add[h];miv[l]+=add[h];
            add[r]+=add[h];val[r]+=add[h];miv[r]+=add[h];
            add[h]=0;
        }
        if(rev[h]){
            rev[l]^=1;rev[r]^=1;rev[h]^=1;
            swap(ch[h][0],ch[h][1]);
        }
    }

    void rotate(int h){//旋转
        int f=fa[h],g=fa[f];
        if(g){
            int c=(f==ch[g][1]);
            ch[g][c]=h;
        }
        fa[f]=h;fa[h]=g;
        int c=(h==ch[f][1]);
        fa[ch[h][!c]]=f;
        ch[f][c]=ch[h][!c];
        ch[h][!c]=f;
        if(f==rt) rt=h;
        pushup(f);
        pushup(h);
    }

    void splay(int h,int aim){//伸展
        static int sta[maxn];
        int top=1;sta[top]=h;
        for(int i=h;fa[i]!=0;i=fa[i])sta[++top]=fa[i];
        for(int i=top;i>=1;--i)pushdown(sta[i]);
        while(fa[h]^aim){
            int f=fa[h],g=fa[f];
            if(g^aim)rotate(f);
            rotate(h);
        }
        pushup(h);
    }

    void newnode(int&h,int f,int val_){
        if(rub_!=-1)h=rub[rub_--];//如果rub是空的，我们就从rub里面找
        else h=++tot;//否则使用新的

        ch[h][0]=ch[h][1]=0;
        fa[h]=f;

        miv[h]=val[h]=val_;
        add[h]=rev[h]=0;
        siz[h]=1;
    }

    void built(int&x,char*data,int l,int r,int f){
        if(l>r)return;
        int mid=(l+r)>>1;
        newnode(x,f,data[mid]);
        built(ch[x][0],data,l,mid-1,x);
        built(ch[x][1],data,mid+1,r,x);
        pushup(x);
    }

    void ini(){//建只含有两个节点的空树
        rub_=-1;tot=0;
        newnode(rt,0,0);
        newnode(ch[rt][1],rt,0);
        pushup(ch[rt][1]);
        pushup(rt);
    }

    void insert(int a,char*data,int l,int r){//把data添加在a的后面，
        int x=id(a),y=id(a+1);
        splay(x,0); splay(y,x);
        built(ch[y][0],data,l,r,y);
        pushup(y);
        pushup(x);
    }

    int id(int k){//返回第k个数，下标是从1开始的
        int h;
        pushdown(rt);
        for(h=rt;siz[ch[h][0]]+1!=k;){
            if(siz[ch[h][0]]+1>k)h=ch[h][0];
            else{
                k-=(siz[ch[h][0]]+1);
                h=ch[h][1];
            }
            pushdown(h);
        }
        return h;
    }
    //以上函数必备，尽量不要修改
    ////////////////////////

    void rubbish(int&rt){
        if(ch[rt][0])rubbish(ch[rt][0]);
        if(ch[rt][1])rubbish(ch[rt][1]);
        rub[++rub_]=rt;
        rt=0;
    }

    void erase(int a,int b){
        int x=id(a-1), y=id(b+1);
        splay(x,0); splay(y,x);
        rubbish(ch[y][0]);
        pushup(y); pushup(x);
    }

    int getmin(int a,int b){
        int x=id(a-1), y=id(b+1);
        splay(x,0); splay(y,x);
        return miv[ch[y][0]];
    }

    void addval(int a,int b,int d){
        int x=id(a-1), y=id(b+1);
        splay(x,0); splay(y,x);
        int w=ch[y][0];
        add[w]+=d;
        val[w]+=d;
        miv[w]+=d;
        pushup(y); pushup(x);
    }

    void reserve(int a,int b){
        int x=id(a-1), y=id(b+1);
        splay(x,0); splay(y,x);
        rev[ch[y][0]]^=1;
    }

}tree;