loj 558 我们的 CPU 遭到攻击

这题很明显是lct，我们只要可以维护黑色点深度和即可。

但是lct维护子树信息好难写啊。
首先边权比较难处理，所以偷懒加虚点表示边。

然后考虑维护子树距离和，需要维护splay上的边权和。
为了可以reverse，还必须维护一个反的距离和。
虚子树的答案更新在access和link连虚边的时候。
好烦啊。

千万不要把splay之前的下传标记写挂，记得只下传本splay的标记。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;

struct node{
    int blcnt;//black cnt
    int non_cnt;//xzs
    ll non_dis;
    ll sumval;//bian quan he
    int val;//bian quan
    ll disl,disr;//disl disr
    bool fl,bl;
    int fa,ch[2];
    void clear(){
        memset(this,0,sizeof(*this));
    }
    void print(){
        cout<<"blcnt: "<<blcnt<<endl;
        cout<<"non_cnt: "<<non_cnt<<endl;
        cout<<"non_dis: "<<non_dis<<endl;
        cout<<"sumval: "<<sumval<<endl;
        cout<<"val: "<<val<<endl;
        cout<<"dislr: "<<disl<<" "<<disr<<endl;
        cout<<"flip: "<<fl<<endl;
        cout<<"bl:"<<bl<<endl;
        cout<<"fa:"<<fa<<endl;
        cout<<"ch[0:1]:"<<ch[0]<<" "<<ch[1]<<endl;
    }
}T[N];

int n,m,k;
bool get(int x){
    return T[T[x].fa].ch[1]==x;
}
bool nroot(int x){
    return T[T[x].fa].ch[0]==x||T[T[x].fa].ch[1]==x;
}
bool ISBLACK(int x){
    return x<=n&&T[x].bl;
}
void pushup(int x){
    //cerr<<"pushup"<<x<<endl;
    int ls=T[x].ch[0],rs=T[x].ch[1];
    T[x].blcnt=T[x].bl+T[ls].blcnt+T[rs].blcnt+T[x].non_cnt;
    T[x].sumval=T[x].val+T[ls].sumval+T[rs].sumval;
    
    T[x].disl=T[x].disr=T[x].non_dis;

    T[x].disl+=T[ls].disl+T[rs].disl+(ISBLACK(x)+T[x].non_cnt+T[rs].blcnt)*(T[ls].sumval+T[x].val);
    T[x].disr+=T[rs].disr+T[ls].disr+(ISBLACK(x)+T[x].non_cnt+T[ls].blcnt)*(T[rs].sumval+T[x].val);
};

void puttag(int x){
    swap(T[x].disl,T[x].disr);
    swap(T[x].ch[0],T[x].ch[1]);
    T[x].fl^=1;
}

void pushdown(int x){
    if (T[x].fl){
        if (T[x].ch[0]) puttag(T[x].ch[0]);
        if (T[x].ch[1]) puttag(T[x].ch[1]);
        T[x].fl=0;
    }
}
void allpushdown(int x){
    if (nroot(x)) allpushdown(T[x].fa);
    pushdown(x);
}


void rotate(int x){
    //cerr<<"roate"<<x<<endl;
    int f=T[x].fa,gx=get(x),xs=T[x].ch[gx^1];
    T[x].fa=T[f].fa; if (nroot(f)) T[T[f].fa].ch[get(f)]=x;
    T[f].fa=x; T[x].ch[gx^1]=f;
    if (xs) T[xs].fa=f; T[f].ch[gx]=xs;
    pushup(f);
    //cerr<<"faf"<<T[1].fa<<" "<<T[2].ch[0]<<" "<<T[2].ch[1]<<endl;
}

void splay(int x){
    //cerr<<"splay"<<x<<endl;
    allpushdown(x);
    for (; nroot(x); rotate(x)){
        int f=T[x].fa;
        if (nroot(f)&&get(f)==get(x)) rotate(f);
    }
    pushup(x);
    //cerr<<"splayend"<<endl;
}

void access(int x){//????
    //cerr<<"access"<<x<<" "<<"fa"<<T[x].fa<<" "<<T[3].fa<<endl;
    int la=0;
    while (1){
        splay(x);
        T[x].non_cnt+=T[T[x].ch[1]].blcnt-T[la].blcnt;
        T[x].non_dis+=T[T[x].ch[1]].disl-T[la].disl;
        T[x].ch[1]=la;
        pushup(x);
        la=x;
        if (!(x=T[x].fa)) break;    
    }
}

void makeroot(int x){
    //cerr<<"makeroot"<<x<<" "<<T[x].fa<<" "<<T[T[x].fa].fa<<" "<<T[T[T[x].fa].fa].fa<<endl;
    access(x);
    //cerr<<"ACCEND"<<endl;
    splay(x);
    //cerr<<"ASM"<<T[1].fa<<" "<<T[2].fa<<" "<<T[3].fa<<" "<<T[3].ch[0]<<endl;
    puttag(x);
    //cerr<<":MEDN"<<endl;
}

void __link(int x,int y){
    //link virtual edge
    //cerr<<"__link"<<x<<" "<<y<<endl;
    makeroot(x);
    makeroot(y);
    //cerr<<"YYB"<<T[y].ch[0]<<endl;
    T[y].fa=x;
    T[x].non_cnt+=T[y].blcnt;
    T[x].non_dis+=T[y].disl;
    pushup(x);
    //cerr<<"ASF__link"<<T[1].fa<<" "<<T[2].fa<<" "<<T[3].fa<<endl;
}
stack<int> s;
map<int,int> mp[N>>1];
void link(int u,int v,int w){
    //cerr<<"link"<<u<<" "<<v<<" "<<w<<endl;
    int cnt=s.top(); s.pop();
    mp[u][v]=mp[v][u]=cnt;
    T[cnt].clear();
    T[cnt].val=w;
    __link(u,cnt);
    __link(v,cnt);
}

void __cut(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
    assert(T[y].ch[0]==x);
    T[y].ch[0]=0;
    T[x].fa=0;
    pushup(y);
}

void cut(int u,int v){
    int cnt=mp[u][v];
    __cut(u,cnt);
    __cut(v,cnt);
    s.push(cnt);
}

void flip(int u){
    makeroot(u);
    T[u].bl^=1;
    pushup(u);
}

void Dfs(int x){
    //cerr<<"Indfs"<<x<<" "<<T[x].fl<<" "<<T[x].ch[0]<<" "<<T[x].ch[1]<<" "<<T[x].sumval<<" "<<T[x].disl<<" "<<T[x].blcnt<<endl;
    if (T[x].ch[0]) Dfs(T[x].ch[0]);
    if (T[x].ch[1]) Dfs(T[x].ch[1]);
}

ll query(int u){
    //cerr<<"query"<<u<<endl;
    makeroot(u);
    //Dfs(u);
    //cerr<<"U"<<u<<endl;
    //cerr<<"query"<<T[u].blcnt<<endl;
    //cerr<<"query"<<T[u].non_dis<<" "<<T[u].non_cnt<<" "<<T[u].ch[0]<<" "<<T[u].ch[1]<<endl;
    //cerr<<"Trifa"<<T[3].fa<<" "<<T[3].val<<endl;
    //cerr<<"query"<<T[u].sumval<<endl;
    return T[u].disl;
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=n+n-1; i>n; --i) s.push(i);
    for (int i=1; i<=m; ++i){
        //cerr<<"DOD"<<i<<endl;
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        //cerr<<u<<" "<<v<<" "<<w<<endl;
        link(u,v,w);
    }
    /*for (int i=1; i<=n+n-1; ++i){
        cerr<<"I"<<i<<endl;
        T[i].print();
        }*/
    //return 0;
    for (int i=1; i<=k; ++i){
        //cerr<<"action:------------------"<<i<<endl;
        char s[10];
        int u,v,w;
        scanf("%s%d",s,&u);
        //cerr<<u<<endl;
        if (s[0]=='C'||s[0]=='L') scanf("%d",&v);
        if (s[0]=='L') scanf("%d",&w);
        switch (s[0]){
        case 'L':
            link(u,v,w);
            break;
        case 'C':
            cut(u,v);
            break;
        case 'F':
            flip(u);
            break;
        case 'Q':
            cout<<query(u)<<'\n';
            break;
        }

        //cerr<<"DODODODDD"<<endl;
        //cerr<<"!!!!!!!"<<endl;
        //for (int i=1; i<n+n; ++i) T[i].print();
        
        //cerr<<"afterall"<<T[1].fa<<" "<<T[2].fa<<" "<<T[3].fa<<endl;
    }
}

差点就是最长代码了，足以看出调试的艰辛。

loj 558 我们的 CPU 遭到攻击

原文：https://www.cnblogs.com/Yuhuger/p/10560697.html