[BZOJ3159] 决战 题解

个人感觉各方面难度高于《在美妙的数学王国中畅游》，也不知道是不是求导的关系，这题 \(luogu\) 难度评级还更低。不过感觉这题作完对 \(LCT\) 理解更顺畅了。

前四个操作简单，关键在第五人格操作。

注意力惊人的注意到我们无法像普通 \(Splay\) 一样，直接对 \(LCT\) 中的 \(Splay\) 进行区间反转。因为 \(LCT\) 中的 \(Splay\) 同时维护树的形态 \(id\) 和权值 \(val\)。

那我们干脆把这俩玩意分别处理，相当于建 \(id\ tree\) 和 \(val\ tree\)。由于 \(Splay\) 的操作都是在根处进行，所以我们只需要对于每个根节点 \(rt\) 记录 \(pos_{rt}\) 表示对应另一棵树中自己的编号，就可以完成查询。小改 \(rotate,link\)，魔改 \(access\)，再加一个 \(setpos\) 用来找 \(pos_{rt}\) 即可。

时间复杂度 \(O(n\log n)\)。

#include<bits/stdc++.h>
#define ll long long
#define fa(x) lct[x].fa
#define fl(x) lct[x].fl
#define mx(x) lct[x].mx
#define mn(x) lct[x].mn
#define sz(x) lct[x].sz
#define ad(x) lct[x].ad
#define val(x) lct[x].val
#define sum(x) lct[x].sum
#define sn(x,i) lct[x].sn[i]
using namespace std;
const int N=1e5+5;
struct node{
    int sn[2],val;ll sum;
    int mx,mn,fa,fl,sz,ad;
}lct[N];int n,m,tp,st[N];
int pos[N],flg;string s;
int check(int x){
    return sn(fa(x),0)!=x&&sn(fa(x),1)!=x;
}int chksn(int x){
    return sn(fa(x),1)==x;
}void push_up(int x){
    sz(x)=sz(sn(x,0))+sz(sn(x,1))+1;
    sum(x)=sum(sn(x,0))+sum(sn(x,1))+val(x);
    mx(x)=max({mx(sn(x,0)),mx(sn(x,1)),val(x)});
    mn(x)=min({mn(sn(x,0)),mn(sn(x,1)),val(x)});
}void push(int x){
    if(!x) return;fl(x)^=1;
    swap(sn(x,0),sn(x,1));
}void down(int x,int a){
    if(!x) return;
    sum(x)+=(ll)sz(x)*a,val(x)+=a;
    ad(x)+=a,mx(x)+=a,mn(x)+=a;
}void push_down(int x){
    if(!x) return;
    if(fl(x)){
        push(sn(x,0));
        push(sn(x,1));
    }down(sn(x,0),ad(x));
    down(sn(x,1),ad(x));
    fl(x)=ad(x)=0;
}void rotate(int x){
    int y=fa(x),z=fa(y),k=chksn(x);
    if(check(y)) pos[x]=pos[y];
    else sn(z,chksn(y))=x;
    fa(x)=z,fa(y)=x,fa(sn(x,1-k))=y;
    sn(y,k)=sn(x,1-k),sn(x,1-k)=y;
    push_up(y);
}void splay(int x){
    st[tp=1]=x;
    for(int i=x;!check(i);i=fa(i)) st[++tp]=fa(i);
    while(tp) push_down(st[tp--]);
    while(!check(x)){
        int y=fa(x),z=fa(y);
        if(!check(y))
            rotate(chksn(x)!=chksn(y)?x:y);
        rotate(x);
    }push_up(x);
}int find(int x,int k){
    push_down(x);
    if(sz(sn(x,0))+1==k) return x;
    if(sz(sn(x,0))>=k) return find(sn(x,0),k);
    return find(sn(x,1),k-sz(sn(x,0))-1);
}void setpos(int x){
    splay(x),splay(pos[x]);
    pos[x]=find(pos[x],sz(sn(x,0))+1);
    splay(pos[x]);
}void access(int x){
    setpos(x);int y=sn(x,1),z=sn(pos[x],1);
    pos[y]=z,fa(z)=0,sn(x,1)=sn(pos[x],1)=0;
    push_up(x),push_up(pos[x]);
    while(fa(x)){
        setpos(x),setpos(fa(x));
        pos[sn(fa(x),1)]=sn(pos[fa(x)],1);
        sn(fa(x),1)=x,fa(sn(pos[fa(x)],1))=0;
        sn(pos[fa(x)],1)=pos[x];
        fa(pos[x])=pos[fa(x)];
        push_up(pos[fa(x)]);
        push_up(fa(x)),x=fa(x);
    }
}void mk(int x){
    access(x),setpos(x);
    push(x),push(pos[x]);
}void split(int x,int y){
    mk(x),access(y),setpos(y);
}void link(int x,int y){
    mk(x),setpos(y),fa(x)=y;
}signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    mn(0)=1e18,cin>>n>>m>>tp;
    for(int i=1;i<=n;i++)
        sz(i)=sz(i+n)=1,pos[i]=i+n,pos[i+n]=i;
    for(int i=1,x,y;i<n;i++)
        cin>>x>>y,link(x,y);
    while(m--){
        int x,y,w;cin>>s>>x>>y;split(x,y);
        if(s=="Increase") cin>>w,down(pos[y],w);
        if(s=="Sum") cout<<sum(pos[y])<<"\n";
        if(s=="Major") cout<<mx(pos[y])<<"\n";
        if(s=="Minor") cout<<mn(pos[y])<<"\n";
        if(s=="Invert") push(pos[y]);
    }return 0;
}