只有&|的判断(20pts)

• 根据&和|的运算规则进行分别枚举

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],b[N];
int main()
{
    string s;
    getline(cin,s);
    int c=0;
    int m=s.size();
    for(int i=0;i<m;i++) //c=1 表示&符号出现过 c=2表示|出现过
    {
        if(s[i]=='&') c=1;
        else if(s[i]=='|') c=2;
    }
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) //输入数字
    {
        cin>>a[i];
    }
    int q;
    cin>>q;  
    int c1=0,c2=0; //统计原来的状态
    for(int i=1;i<=n;i++)
    {
        if(a[i]==1) c1++;
        else c2++;
    }
    while(q--)
    {
        int t;
        cin>>t;
        if(a[t]==1) //进行变化
        {
            c1++,c2--;
        }
        else
        {
            c2++,c1--;
        }
        if(c==1) //都是&的操作
        {
            if(c1==n) cout<<1<<endl; //都是1才是1
            else cout<<0<<endl;
        }
        else //都是|的操作
        {
            if(c1!=0) cout<<1<<endl; //只要有一个是1就是1
            else cout<<0<<endl;
        }
        if(a[t]==1) //还原
        {
            c1--,c2++;
        }
        else
        {
            c2--,c1++;
        }
    }
	return 0;
}

模拟($O(qn)$)

• 利用表达式计算每次修改以后的结果

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
char str[N]; //表达式
int w[N]; //值
stack<int> stk;
int n;
int main()
{
    cin.getline(str,N); //表达式
    cin>>n; //未知数个数
    for(int i=1;i<=n;i++) cin>>w[i];
    int lens=strlen(str);
    int q;
    cin>>q;
    while(q--)
    {
        int x;
        cin>>x;
        w[x]=!w[x];
        for(int i=0;str[i];i++)
        {
            if(str[i]==' ') continue; //空格
            if(str[i]=='x') //未知数
            {
                int j=i+1;
                int x=0;
                while(j<lens&&isdigit(str[j])) //取出连续的一段
                {
                    x=x*10+str[j]-'0';
                    j++;
                }
                j--;
                stk.push(w[x]);
                i=j;
                continue;
            }
            if(str[i]=='!') //非
            {
                int x=stk.top();
                stk.pop();
                stk.push(!x);
            }
            if(str[i]=='&'||str[i]=='|') //两个运算
            {
                int b=stk.top();stk.pop();
                int a=stk.top();stk.pop();
                if(str[i]=='&')
                {
                    if(a&&b) stk.push(1);
                    else stk.push(0);
                }
                else
                {
                    if(a||b) stk.push(1);
                    else stk.push(0);
                }
            }
        }
        cout<<stk.top()<<endl; //改变了以后的结果
        stk.pop();
        w[x]=!w[x];
    }
    return 0;
}

表达式树优化(100pts)

• 第一遍dfs计算表达式树，第二遍dfs根据表达式树中的节点的值，判断是否对结果有影响。

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m;
int h[N],e[N],ne[N],idx;
int w[N];
char c[N];
bool st[N];
int stk[N],top;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs1(int u)
{
    if(!c[u]) return w[u];//当前u是叶子节点
    if(c[u]=='!') w[u]=!dfs1(e[h[u]]); //取反是子树的相反值
    else
    {
        int a=e[h[u]],b=e[ne[h[u]]];
        if(c[u]=='&') w[u]=dfs1(a)&dfs1(b);//递归计算左右子树
        else w[u]=dfs1(a)|dfs1(b);
    }
    return w[u];//返回当前子树的计算结果
}
void dfs2(int u)
{
    st[u]=true;
    if(!c[u]) return ;//叶子节点
    if(c[u]=='!') dfs2(e[h[u]]); //可以影响到子树
    else
    {
        int a=e[h[u]],b=e[ne[h[u]]];
        if(c[u]=='&')
        {
            if(w[a]) dfs2(b); //左边是1,右子树可以影响结果
            if(w[b]) dfs2(a); //右边是1，左子树可以影响结果
        }
        else
        {
            if(!w[a]) dfs2(b); //左边是0，右子树可以影响结果
            if(!w[b]) dfs2(a); //右边是1，左子树可以影响结果
        }
    }
}
int main()
{
    string s;
    getline(cin,s);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    memset(h,-1,sizeof h);
    m=n;//数字节点
    for(int i=0;i<s.size();i++)
    {
        if(s[i]==' ') continue;
        if(s[i]=='x') //取出数字
        {
            int j=i+1,x=0;
            while(j<s.size()&&isdigit(s[j]))
            {
                x=x*10+s[j]-'0';
                j++;
            }
            stk[++top]=x;
            i=j;
        }
        else if(s[i]=='!') //非运算符
        {
            c[++m]=s[i];
            add(m,stk[top--]);
            stk[++top]=m;
        }
        else //| 或 & 的运算符
        {
            c[++m]=s[i];
            add(m,stk[top--]);
            add(m,stk[top--]);
            stk[++top]=m;
        }
    }
    int res=dfs1(m); //从根节点开始计算
    dfs2(m);
    int q;
    cin>>q;
    while(q--) //查询
    {
        int x;
        cin>>x;
        if(st[x]) cout<<(res^1)<<endl;
        else cout<<res<<endl;
    }
    return 0;
}