AC：10

WA：20

TLE：70

用了一个类似线段树的思想，把字符串反过来递归建树，遇到&和|就递归两个分支，遇到!就递归一个分支，当是&和|的时候先左再右，每次选择从右往左第一个没走过的符号，如果是数字就返回。

但是我算出来的复杂度是$O(size+q(\log size))$（size指字符串长度

想象中是AC，但是这个会TLE？求解

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
string s;
int dfn=0;
struct Tree
{
	int fa,ls,rs;//fa:父节点指针  &和|的ls和rs都存在,!只有ls,数字没有 
	int op;//0:数字 1:& 2:| 3:! 
	int val;//结点逻辑值 
}tree[MAXN];
int p[MAXN],a[MAXN];//p[num]:变量num在树中对应的节点编号 
bool vis[MAXN];
bool digit(char ch)//判数字 
{
	if(ch>='0' && ch<='9') return true;
	else return false;
}
void Build(int pos)//pos:字符串的位置
{
	if(pos<0) return;
	int i;
	vis[pos]=true;
	dfn++;//时间戳 
	if(digit(s[pos]))//如果是数字 
	{
		int vari=0;
		for(i=pos;digit(s[i]);i--)//把所有数位以及那个x都标记 
		{
			vari=vari*10+(s[i]-'0');
			vis[i]=true;
		}
		vis[i]=true;
		tree[dfn].val=a[vari];//叶子节点的初值 
		tree[dfn].op=0;
		p[vari]=dfn; 
		return;//因为数字已经是最底层的符号了,所以处理完数字就return 
	}
	else
	{
		if(s[pos]=='!')
		{
			int u=dfn;//u是记录当前pos的时间戳 
			int l=dfn+1;//!只有左儿子,而左儿子的时间戳一定是父节点的时间戳+1 
			Build(pos-1);//递归建树 
			tree[l].fa=u;//父节点指针 
			tree[u].op=3;//记录符号类型 
			tree[u].ls=l;
			tree[u].val=!(tree[l].val);
			//tree[u].val表示以u为根节点的子树对应的表达式运算完毕后的逻辑值 
		}
		else
		{
			int u=dfn;
			int l=dfn+1;
			Build(pos-1);//递归左子树 
			tree[l].fa=u;//父节点 
			for(i=pos-1;vis[i];i--);//跳过所有左子树走过的位置 
			int r=dfn+1;//dfn是全局的,所以r就是左子树中的最大时间戳+1 
			Build(i);//右子树 
			tree[r].fa=u;//父节点,too 
			if(s[pos]=='&')
			{
				tree[u].op=1;
				tree[u].ls=l;
				tree[u].rs=r;
				tree[u].val=tree[l].val&tree[r].val;
			}
			else
			{
				tree[u].op=2;
				tree[u].ls=l;
				tree[u].rs=r;
				tree[u].val=tree[l].val|tree[r].val;
			}
		}
	}
	return;
}
void Update(int u)//每次询问 
{
	if(tree[u].val==0) tree[u].val=1;
	else tree[u].val=0;//其实就是取反 
	int v=tree[u].fa;
	//从u开始往上走,因为每次改变的叶子节点只会影响它到根节点路径上的所有点 
	while(v!=0)
	{
		switch(tree[v].op)
		{
			case 1:
			{
				tree[v].val=tree[tree[v].ls].val&tree[tree[v].rs].val;
				break;
			}
			case 2:
			{
				tree[v].val=tree[tree[v].ls].val|tree[tree[v].rs].val;
				break;
			}
			case 3:
			{
				tree[v].val=!tree[tree[v].ls].val;
				break;
			}
		}
		v=tree[v].fa;
	}
	return;
}
int main()
{
	int n,m,q,i,j;
	char ch;
	while(scanf("%c",&ch))
	{
		if(ch=='\n') break;
		else if(ch==' ') continue;
		s+=ch;
	}
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	int len=s.size();
	Build(len-1);
	scanf("%d",&q);
	for(i=1;i<=q;i++)
	{
		int u;
		scanf("%d",&u);
		int st=p[u];//找到这次修改的变量在树中的哪个节点上 
		Update(st);
		printf("%d\n",tree[1].val);//相当于是修改后表达式的值 
		Update(st);//第二次相当于还原值 
	}
	return 0;
}