题目概述

给出一个逻辑运算树，每个节点有一个逻辑运算或输入框（ $0$ 或 $1$ ）以及 $0/1/2$ 个儿子（根据符号定）。问每次只把所有输入框中的一个改成相反的（ $0\to 1,1\to 0$ ）之后根节点的数。

解题报告

倍增就行了，记 $ST[x][j][0/1]$ 表示 $x$ 是 $0/1$ ，往上走 $2^j$ 次得到的数，瞎转移。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=1000000,Log=20;

int ID[256],n,ty[maxn+5],son[maxn+5][2];bool val[maxn+5];
int dep[maxn+5],fa[maxn+5][Log+5];bool ST[maxn+5][Log+5][2];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
void Pre(int x){
    if (ty[x]>3) return;if (son[x][0]) Pre(son[x][0]);if (son[x][1]) Pre(son[x][1]);
    if (ty[x]==0) val[x]=val[son[x][0]]&val[son[x][1]];
    else if (ty[x]==1) val[x]=val[son[x][0]]|val[son[x][1]];
    else if (ty[x]==2) val[x]=val[son[x][0]]^val[son[x][1]];
    else if (ty[x]==3) val[x]=val[son[x][0]]^1;
}
#define Son(x) ((x)==son[pre][1])
void Dfs(int x,int pre=0){
    if (pre){fa[x][0]=pre;dep[x]=dep[pre]+1;
        if (ty[pre]==3) ST[x][0][0]=1,ST[x][0][1]=0;
        else if (ty[pre]==0) ST[x][0][0]=0&val[son[pre][Son(x)^1]],ST[x][0][1]=1&val[son[pre][Son(x)^1]];
        else if (ty[pre]==1) ST[x][0][0]=0|val[son[pre][Son(x)^1]],ST[x][0][1]=1|val[son[pre][Son(x)^1]];
        else if (ty[pre]==2) ST[x][0][0]=0^val[son[pre][Son(x)^1]],ST[x][0][1]=1^val[son[pre][Son(x)^1]];
        for (int j=1;j<=Log;j++) fa[x][j]=fa[fa[x][j-1]][j-1];
        for (int j=1;j<=Log;j++) ST[x][j][0]=ST[fa[x][j-1]][j-1][ST[x][j-1][0]],ST[x][j][1]=ST[fa[x][j-1]][j-1][ST[x][j-1][1]];
    }
    if (son[x][0]) Dfs(son[x][0],x);if (son[x][1]) Dfs(son[x][1],x);
}
inline int getans(int x) {int D=dep[x],ans=val[x]^1;for (int j=Log;~j;j--) if (D>>j&1) ans=ST[x][j][ans],x=fa[x][j];return ans;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    ID['A']=0;ID['O']=1;ID['X']=2;ID['N']=3;ID['I']=4;
    for (int i=(readi(n),1);i<=n;i++){
        char ch=readc();while (ch!='A'&&ch!='O'&&ch!='X'&&ch!='N'&&ch!='I') ch=readc();ty[i]=ID[ch];
        if (ch=='A'||ch=='O'||ch=='X') readi(son[i][0]),readi(son[i][1]);
        else if (ch=='N') readi(son[i][0]); else {int x;readi(x);val[i]=x;}
    }
    Pre(1);Dfs(1);for (int i=1;i<=n;i++) if (ty[i]>3) putchar(getans(i)+48);return 0;
}