70分RE 记录

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
stack<int>s;
int tot;int rt;
int son1[200005];
int son2[200005];
int pnt[200005];
int v[200005];
bool l[200005];
bool pv[200005];
int iread(){
    int tmp=0;char c;
    while(1){c=getchar();if(c==-1)return -1;if(c>='0'&&c<='9')break;}
    while(1){
        if(c>='0'&&c<='9'){
            tmp=(tmp<<3)+(tmp<<1);tmp+=c-'0';
        }else return tmp;
        c=getchar();
    }return tmp;
}
void pt(int x){
    if(x>9){
        pt(x/10);
    }
    putchar(x%10+'0');
}
void read(){
	int c;
	while(1){
		c=getchar();
        if(c==' ')continue;
        else if(c=='x'){
			int tmp=iread();
			s.push(tot);
			pnt[tot]=tmp;
			tot++;
		}else if(c=='!'){
			son1[tot]=s.top();
			pnt[tot]=-1;
            s.pop();
			s.push(tot);
			tot++;
		}else if(c=='|'){
			son1[tot]=s.top();
            s.pop();
			son2[tot]=s.top();
            s.pop();
            s.push(tot);
			pnt[tot]=-2;
			tot++;
		}else if(c=='&'){
			son1[tot]=s.top();
            s.pop();
			son2[tot]=s.top();
            s.pop();
            s.push(tot);
			pnt[tot]=-3;
			tot++;
		}else return;
	}
}
bool f(int x){
    if(pnt[x]>0){
        pv[x]=v[pnt[x]];
        return v[pnt[x]];
    }else{
        if(pnt[x]==-1){
           bool tmp=!f(son1[x]);
           pv[x]=tmp;
           return tmp;
        }
        else if(pnt[x]==-2){
            bool x1=f(son1[x]);
            bool x2=f(son2[x]);
            pv[x]=(x1||x2);
            return (x1||x2);
        }
        else if(pnt[x]==-3){
            bool x1=f(son1[x]);
            bool x2=f(son2[x]);
            pv[x]=(x1&&x2);
            return (x1&&x2);
        }
    }
    return 0;
}
void dfs(int x,bool lmt){
	if(pnt[x]>0){
        l[pnt[x]]=lmt;
    }else{
        if(pnt[x]==-1){
            dfs(son1[x],lmt);
        }
        else if(pnt[x]==-2){
            bool x1=pv[son1[x]];
            bool x2=pv[son2[x]];
            if(x1&&x2){
                dfs(son1[x],0);
                dfs(son2[x],0);
            }
            else if(x1||x2){
                dfs(son1[x],x1&&lmt);
                dfs(son2[x],x2&&lmt);
            }else{
                dfs(son1[x],lmt);
                dfs(son2[x],lmt);
            }
        }
        else if(pnt[x]==-3){
            bool x1=pv[son1[x]];
            bool x2=pv[son2[x]];
            if(x1&&x2){
                dfs(son1[x],lmt);
                dfs(son2[x],lmt);
            }
            else if(x1||x2){
                dfs(son1[x],(!x1)&&lmt);
                dfs(son2[x],(!x2)&&lmt);
            }else{
                dfs(son1[x],0);
                dfs(son2[x],0);
            }
        }
    }
}
int main(){
	memset(son1,-1,sizeof(son1));
	memset(son2,-1,sizeof(son2));
	read();
    int n=iread();
    ;
    for(int i=1;i<=n;i++){
        v[i]=iread();
    }
    ;
    bool i=f(tot-1);
    dfs(tot-1,1);
    int q=iread();
    while(q--){
        int x=iread();
        pt(l[x]?!i:i);
        putchar('\n');
    }
    return 0;
}

（O2优化）