splay操作集合

下傳标記

void back(ll x,ll y){
    a[x]+=y,ans[x]+=y,add[x]+=y;
}
           

更新目前點的答案

void update(ll x){
    ans[x]=max(a[x],max(ans[tr[x][]],ans[tr[x][]]));
}
           

把标記傳給兒子

void clear(ll x){
    if (tr[x][]) back(tr[x][],add[x]);
    if (tr[x][]) back(tr[x][],add[x]);
    add[x]=;
}
           

判斷點x是它父親的左兒子還是右兒子

ll son(ll x){
    return tr[fa[x]][]==x;
}
           

把x旋到x的父親

void rotate(ll x){
    ll k=son(x),y=fa[x];
    if (tr[x][!k]) fa[tr[x][!k]]=y;
    if (fa[y]) tr[fa[y]][son(y)]=x;
    fa[x]=fa[y],fa[y]=x,tr[y][k]=tr[x][!k],tr[x][!k]=y;
    update(y),update(x);
}
           

釋放從x到y的标記

void remove(ll x,ll y){
    d[]=;
    while (x!=y){
        d[++d[]]=x,x=fa[x];
    }
    while (d[]) clear(d[d[]--]);
}
           

把x旋到y的兒子

void splay(ll x,ll y){
    remove(x,y);
    while (fa[x]!=y){
        if (fa[fa[x]]!=y)
            rotate((son(x)==son(fa[x]))?fa[x]:x);
        rotate(x);
    }
}
           

查找排名為x的點

ll find(ll x){
    ll rk=,nw=rt;
    while (){
        if (tr[nw][] && siz[tr[nw][]]+rk>=x) nw=tr[nw][];else{
            rk+=siz[tr[nw][]];
            if (rk+==x){
                splay(nw,);
                rt=nw;
                return nw;
            }
            rk+=,nw=tr[nw][];
        }
    }
}
           

查詢區間x，y

if (ch=='Q'){
            scanf("uery%lld%lld\n",&l,&r);
            l++,r++;
            x=find(l-);
            y=find(r+);
            splay(x,);
            rt=x;
            splay(y,x);
            printf("%lld\n",(ans[tr[y][]]+mo)%mo);
        }
           

在區間x，y中+z

if (ch=='A'){
            scanf("dd%lld%lld%lld\n",&l,&r,&z);
            l++,r++;
            x=find(l-),y=find(r+);
            splay(x,),splay(y,x);
            rt=x;
            back(tr[y][],z);
        }
           

在x前插入y

if (ch=='I'){
            scanf("nsert%lld%lld\n",&l,&r);
            x=find(l);
            y=find(l+);
            splay(x,),splay(y,x);
            rt=x;
            tr[y][]=++n;
            fa[n]=y;
            a[n]=r;
            p[n]=r*r%mo;
            update(n);
            splay(n,);
            rt=n;
        }