[CSP-J 2020] 表达式

知识点

表达式树、栈、布尔运算、敏感性分析

解题思路

用栈解析后缀表达式，建立叶子为变量的表达式树，并按节点建立顺序求原值。再从根往下传播“该节点取反是否改变根值”：非运算直接传递；与运算只有兄弟值为1时传递；或运算只有兄弟值为0时传递。每个变量仅出现一次，故询问答案为原根值异或该变量的影响标记。

正确性说明

节点编号按后缀处理顺序建立，孩子总先于父亲，原值可按编号递增计算。根值改变需要沿唯一根路径的每个父运算都对该孩子敏感；上述三条传播规则恰为真值表给出的充要条件。所有变量各出现一次，所以不存在同一变量多处变化导致的相互作用。

易错点

询问修改是临时的，不累计；表达式可达一百万字符，使用getline；避免递归遍历深链；变量编号可能多位。

复杂度

时间O(|s|+n+q)，空间O(|s|+n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Node{char op;int l,r,id,val;};
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);string s,t;getline(cin,s);int n;cin>>n;vector<int>a(n+1);for(int i=1;i<=n;++i)cin>>a[i];
 vector<Node>v;vector<int>st,leaf(n+1);istringstream in(s);
 while(in>>t){int u=v.size();if(t[0]=='x'){int x=stoi(t.substr(1));v.push_back({'x',-1,-1,x,a[x]});leaf[x]=u;}
 else if(t=="!"){int l=st.back();st.pop_back();v.push_back({'!',l,-1,0,!v[l].val});}
 else{int r=st.back();st.pop_back();int l=st.back();st.pop_back();v.push_back({t[0],l,r,0,t=="&"?(v[l].val&v[r].val):(v[l].val|v[r].val)});}st.push_back(u);}
 int root=st.back();vector<char>aff(v.size(),0);aff[root]=1;
 for(int u=(int)v.size()-1;u>=0;--u){auto z=v[u];if(z.op=='!')aff[z.l]=aff[u];else if(z.op=='&'){aff[z.l]=aff[u]&&v[z.r].val;aff[z.r]=aff[u]&&v[z.l].val;}else if(z.op=='|'){aff[z.l]=aff[u]&&!v[z.r].val;aff[z.r]=aff[u]&&!v[z.l].val;}}
 int q,x;cin>>q;while(q--){cin>>x;cout<<(v[root].val^aff[leaf[x]])<<'\n';}}