1719 - [CSP-J2020] 表达式

#include<bits/stdc++.h>
using namespace std;
const int N=1000100;
int cnt,k,x[N],w[N],ids[N],ans,root,st[N];
string s;
struct node{
	int type,data;
}a[N];
bool isnum(char c){
	if(c>='0'&&c<='9') return true;
	return false;
}
bool isop(char c){
	if(c=='&'||c=='!'||c=='|') return true;
	return false;
}

void change(){
	int type=1,data=0;
	for(int i=0;i<s.size();i++){
		char x=s[i];
		if(x=='x') type=1,data=0;
		else if(isnum(x)) data=data*10+x-'0';
		else if(isop(x)) type=0,data=x;
		else a[++cnt].type=type,a[cnt].data=data;
	}
	a[++cnt].type=type,a[cnt].data=data;
}

struct tree{
	int l,r,type,data;
}tr[N*2];

void build(){
	stack<int >st;
	for(int i=1;i<=cnt;i++){
		if(a[i].type){
			tr[++k].data=a[i].data;
			tr[k].l=0,tr[k].r=0,tr[k].type=1;
			w[k]=x[a[i].data];
			ids[a[i].data]=k;//定位回来，题目告诉你修改的第五个x5  在树上是第K个 
			st.push(k);
		}
		else if(a[i].data=='!'){
			int t=st.top();
			st.pop();
			tr[++k].data=a[i].data;
			tr[k].l=t,tr[k].r=0,tr[k].type=0;
			w[k]=!w[t]; 
			st.push(k);
		}
		else if(a[i].data=='&'){
			int t1=st.top();
			st.pop();
			int t2=st.top();
			st.pop();
			tr[++k].data=a[i].data;
			tr[k].l=t2,tr[k].r=t1,tr[k].type=0;
			w[k]=w[t1]&w[t2];
			st.push(k);
		}
		else if(a[i].data=='|'){
			int t1=st.top();
			st.pop();
			int t2=st.top();
			st.pop();
			tr[++k].data=a[i].data;
			tr[k].l=t2,tr[k].r=t1,tr[k].type=0;
			w[k]=w[t1]|w[t2];
			st.push(k);
		}
	}
	ans=w[st.top()];
	root=st.top();
}
void dfs(int rt){
	if(tr[rt].type==1) return;
	if(tr[rt].data=='!'){
		int l=tr[rt].l,r=tr[rt].r;
		st[l]=1;
		dfs(l);
	}
	else if(tr[rt].data=='&'){
		int l=tr[rt].l,r=tr[rt].r;
		if(w[l]==1&&w[r]==1){
			st[l]=1;dfs(l);
			st[r]=1;dfs(r);
		}
		else if(w[l]==1&&w[r]==0){
			st[r]=1;dfs(r);
		}
		else if(w[l]==0&&w[r]==1){
			st[l]=1;dfs(l);
		}
	}
	else if(tr[rt].data=='|'){
		int l=tr[rt].l,r=tr[rt].r;
		if(w[l]==0&&w[r]==0){
			st[l]=1;dfs(l);
			st[r]=1;dfs(r);
		}
		else if(w[l]==1&&w[r]==0){
			st[l]=1;dfs(l);
		}
		else if(w[l]==0&&w[r]==1){
			st[r]=1;dfs(r);
		}
	}
}
int main(){
	getline(cin,s);
	change();
	int n;cin>>n;
	for(int i=1;i<=n;i++)	scanf("%d",&x[i]);
	build();
	dfs(root);
	int q;cin>>q;
	for(int i=1;i<=q;i++){
		int y;
		scanf("%d",&y);
		if(st[ids[y]]) cout<<!ans<<"\n";
		else cout<<ans<<"\n";
	}
	return 0;
}