「SHOI2014」三叉神经树

给你一颗由\(n\)个非叶子结点和\(2n+1\)个叶子结点构成的完全三叉树，每个叶子结点有一个输出：\(0\)或\(1\)，每个非叶子结点的输出为自己的叶子结点中较多的那一种状态。

有\(q\)次修改操作，每次修改一个叶子结点的输出，求每次修改后根结点的输出。

\(n\leq 5\times 10^5,q\leq 5\times 10^5\).

不难发现每个节点有两种可能的情况：

1.三个儿子输出均为\(0/1\)。

2.两个儿子输出为\(0/1\)，剩下一个儿子与之相反。

为了方便起见，我们简称第一种情况的点为1类点，第二种情况的点为2类点。

我们发现，一个点的输出被改变，只会影响它的连续若干位祖先。

同时，如果对1类点的任意一个儿子进行修改操作，并不会影响它自身的输出，同样也不会影响这个点的任何一个祖先，只是单纯的把这个点变成了2类点罢了。

而如果对2类点的一个儿子进行修改操作，则会有以下两种可能的结果：

1.这个点变成了1类点。
2.这个点的输出被改变了，并且这种改变还会向父亲传递，直到遇到第一个1类点或是输出与这个点不同的点。

我们定义以下状态：

状态\(0\)：输出\(0\)的2类点
状态\(1\)：输出\(1\)的2类点
状态\(2\)：1类点

这样问题就变成了求连续的最长\(0/1\)链，在序列上可以利用线段树上二分处理，而在树上我们则考虑利用树链剖分来进行维护。

当一个叶子结点输出修改后：

如果父亲结点输出未改变，则父亲结点一定在1类点和2类点之间进行了转化，对应线段树上单点修改。
如果父亲结点输出改变了，那么利用线段树二分自下而上找到被修改的祖先中深度最浅的。并且这一条链上所有的点都是2类点，在二分的过程中直接反转状态即可。

时间复杂度为\(\Omicron(n\log^2 n)\).

这里还要注意一个额外的细节，我们的线段树虽然维护了2类点的输出，但1类点的输出我们并不知晓，不过好在每次有关1类点的操作都是单点操作，所以我们可以额外开一个数组维护1类点的输出。

LCT做法挖坑！！！

code

#include<bits/stdc++.h>

using namespace std;

const int maxn=500005;

int n,q,fa[maxn*3],son[maxn][3],a[maxn*3];

int wss[maxn],topf[maxn],dfn[maxn],idx[maxn],dfs_clock,siz[maxn];

inline int read(){

    int res=0,f_f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-') f_f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch-'0'),ch=getchar();

    return res*f_f;

}

namespace SEG{

    int tp[maxn<<2],rev[maxn<<2];

    inline void push_up(int o){

        int ls=o<<1,rs=o<<1|1;

        if(tp[ls]!=tp[rs]||tp[ls]==2) tp[o]=2;

        else tp[o]=tp[ls];

    }

    inline void modify(int o){

        tp[o]^=1,rev[o]^=1;

    }

    inline void push_down(int o){

        if(!rev[o]) return;

        tp[o<<1]^=1,tp[o<<1|1]^=1,rev[o]=0;

        rev[o<<1]^=1,rev[o<<1|1]^=1;

    }

    inline int update_tp(int o,int l,int r,int ql,int qr,int id){

        int mid=l+r>>1,res;

        if(ql<=l&&r<=qr){

            if(tp[o]!=2){

                if(tp[o]==id){

                    modify(o);

                    return l;

                }

                return 0;

            }

            if(l==r) return 0;

            push_down(o);

            res=update_tp(o<<1|1,mid+1,r,ql,qr,id);

            if(res==mid+1){

                int x=update_tp(o<<1,l,mid,ql,qr,id);

                if(x) res=x;

            }

            push_up(o);

            return res;

        }

        push_down(o);

        if(qr<=mid) res=update_tp(o<<1,l,mid,ql,qr,id);

        else if(ql>mid) res=update_tp(o<<1|1,mid+1,r,ql,qr,id);

        else{

            res=update_tp(o<<1|1,mid+1,r,ql,qr,id);

            if(res==mid+1){

                int x=update_tp(o<<1,l,mid,ql,qr,id);

                if(x) res=x;

            }

        }

        push_up(o);

        return res;

    }

    inline void update_p(int o,int l,int r,int x,int v){

        if(l==r&&l==x){

            tp[o]=v;

            return;

        }

        int mid=l+r>>1;

        push_down(o);

        if(x<=mid) update_p(o<<1,l,mid,x,v);

        else update_p(o<<1|1,mid+1,r,x,v);

        push_up(o);

    }

    inline int query(int o,int l,int r,int x){

        if(l==r&&l==x) return tp[o];

        int mid=l+r>>1;

        push_down(o);

        if(x<=mid) return query(o<<1,l,mid,x);

        else return query(o<<1|1,mid+1,r,x);

    }

}

inline void dfs1(int u,int cur){

    siz[u]=1;

    for (int i=0;i<3;i++){

        int x=son[u][i];

        if(!x) continue;

        dfs1(x,u),siz[u]+=siz[x];

        if(!wss[u]||siz[x]>siz[wss[u]]) wss[u]=x;

    }

    int res=(a[u]<=1)?0:1;

    if(cur) a[cur]+=res;

}

inline void dfs2(int u,int cur){

    dfn[u]=++dfs_clock,idx[dfs_clock]=u;

    SEG::update_p(1,1,n,dfn[u],(a[u]!=0&&a[u]!=3)?a[u]-1:2);

    topf[u]=cur,a[u]=(a[u]<=1)?0:1;

    if(!wss[u]) return;

    dfs2(wss[u],cur);

    for (int i=0;i<3;i++){

        int x=son[u][i];

        if(!x||x==wss[u]) continue;

        dfs2(x,x);

    }

}

inline int update_range(int x,int id){

    if(!x) return 0;

    int res=SEG::update_tp(1,1,n,dfn[topf[x]],dfn[x],id);

    if(res^dfn[topf[x]]) return res;

    int cur=update_range(fa[topf[x]],id);

    if(cur) return cur;

    return res;

}

inline int get_p(int x){

    int res=SEG::query(1,1,n,dfn[x]);

    if(res^2) return res;

    else return a[x];

}

int main(){

    n=read();

    for (int i=1;i<=n;i++){

        for (int j=0;j<3;j++){

            int x=read();

            fa[x]=i;

            if(x<=n) son[i][j]=x;

        }

    }

    for (int i=n+1;i<=n*3+1;i++){

        a[i]=read(),a[fa[i]]+=a[i];

    }

    dfs1(1,0),dfs2(1,1);

    q=read();

    while(q--){

        int x=read(),y=update_range(fa[x],a[x]);

        int now=fa[idx[y]!=0?idx[y]:x];

        a[x]^=1;

        if(now){

            int res=SEG::query(1,1,n,dfn[now]);

            if(res!=2) a[now]=res;

            if(res==a[x]) SEG::update_p(1,1,n,dfn[now],2);

            else SEG::update_p(1,1,n,dfn[now],a[now]);

        }

        printf("%d\n",get_p(1));

    }

    return 0;

}

巴特西

「SHOI2014」三叉神经树

「SHOI2014」三叉神经树

LCT做法挖坑！！！

最新文章

热门文章