#include #include #include #define ls (p << 1) #define rs (ls | 1) using namespace std; const int S = 2e6; const int N = 2e5; int n,q,len,a[N + 5],tot; char s[S + 5]; int rev[N + 5],type[N + 5]; int to[N + 5],pre[N + 5],first[N + 5]; inline void add(int u,int v) { static int tot = 0; to[++tot] = v,pre[tot] = first[u],first[u] = tot; } int fa[N + 5],dep[N + 5],son[N + 5],sz[N + 5],top[N + 5],id[N + 5],ed[N + 5],rt; namespace BUILDER { int st[N + 5],top; char x; int num; void build() { tot = n; s[len] ^ ' ' && (s[++len] = ' '); for(register int i = 1;i <= len;++i) if(s[i] == ' ') { if(x == '!') rev[st[top]] ^= 1; else if(x == 'x') st[++top] = num,num = 0; else type[++tot] = x == '|', fa[st[top]] = fa[st[top - 1]] = tot, add(tot,st[top]),add(tot,st[top - 1]), st[--top] = tot; x = 0; } else if(s[i] >= '0' && s[i] <= '9') num = num * 10 + (s[i] ^ '0'); else x = s[i]; } } struct Value { int cnt,v; inline Value(int x = 0) { if(x) cnt = 0,v = x; else cnt = v = 1; } inline Value(int a,int b) { cnt = a,v = b; } inline Value operator*(const Value &o) const { return Value(cnt + o.cnt,v * o.v); } inline Value operator/(const Value &o) const { return Value(cnt - o.cnt,v / o.v); } inline int operator()() const { return cnt ? 0 : v; } } g[N + 5]; int f[N + 5]; struct func { int k,b; inline func(int x = 1,int y = 0) { k = x,b = y; } inline func operator*(const func &o) const { return func(k * o.k,k * o.b + b); } } seg[(N << 2) + 5],w[N + 5]; void build(int p,int tl,int tr) { if(tl == tr) { seg[p] = w[tl]; return ; } int mid = tl + tr >> 1; build(ls,tl,mid),build(rs,mid + 1,tr); seg[p] = seg[ls] * seg[rs]; } void insert(int x,func k,int p,int tl,int tr) { if(tl == tr) { seg[p] = k; return ; } int mid = tl + tr >> 1; x <= mid ? insert(x,k,ls,tl,mid) : insert(x,k,rs,mid + 1,tr); seg[p] = seg[ls] * seg[rs]; } inline void insert(int p) { if(!rev[p] && !type[p]) insert(id[p],func(g[p](),0),1,1,tot); else if(!rev[p] && type[p]) insert(id[p],func(g[p](),1 - g[p]()),1,1,tot); else if(rev[p] && !type[p]) insert(id[p],func(-g[p](),1),1,1,tot); else if(rev[p] && type[p]) insert(id[p],func(-g[p](),g[p]()),1,1,tot); } func query(int l,int r,int p,int tl,int tr) { if(l <= tl && tr <= r) return seg[p]; int mid = tl + tr >> 1; if(l <= mid && r > mid) return query(l,r,ls,tl,mid) * query(l,r,rs,mid + 1,tr); else if(l <= mid) return query(l,r,ls,tl,mid); else return query(l,r,rs,mid + 1,tr); } void dfs1(int p) { sz[p] = 1,f[p] = p <= n ? a[p] : 1; for(register int i = first[p];i;i = pre[i]) { dep[to[i]] = dep[p] + 1,dfs1(to[i]),sz[p] += sz[to[i]],f[p] *= (type[p] ? 1 - f[to[i]] : f[to[i]]); if(!son[p] || sz[son[p]] < sz[to[i]]) son[p] = to[i]; } (type[p] ^ rev[p]) && (f[p] ^= 1); } void dfs2(int p) { static int tot = 0; id[p] = ++tot,g[p] = p <= n ? a[p] : 1; if(son[p]) top[son[p]] = top[p],dfs2(son[p]),ed[p] = ed[son[p]]; else ed[p] = p; for(register int i = first[p];i;i = pre[i]) if(to[i] ^ son[p]) top[to[i]] = to[i],dfs2(to[i]),g[p] = g[p] * (type[p] ? 1 - f[to[i]] : f[to[i]]); } void update(int p) { for(;p;p = fa[p]) { insert(p),p = top[p]; func x = query(id[p],id[ed[p]],1,1,tot); g[fa[p]] = g[fa[p]] / (type[fa[p]] ? 1 - f[p] : f[p]), f[p] = x.k * (type[ed[p]] ^ 1) + x.b, g[fa[p]] = g[fa[p]] * (type[fa[p]] ? 1 - f[p] : f[p]); } } int main() { //freopen("expr.in","r",stdin),freopen("expr.out","w",stdout); char ch = getchar(); do s[++len] = ch,ch = getchar(); while(ch ^ '\r' && ch ^ '\n'); scanf("%d",&n),BUILDER::build(); for(register int i = 1;i <= tot;++i) if(!fa[i]) rt = i; for(register int i = 1;i <= n;++i) scanf("%d",a + i); dep[rt] = 1,top[rt] = rt,dfs1(rt),dfs2(rt); for(register int i = 1;i <= tot;++i) if(!rev[i] && !type[i]) w[id[i]] = func(g[i](),0); else if(!rev[i] && type[i]) w[id[i]] = func(g[i](),1 - g[i]()); else if(rev[i] && !type[i]) w[id[i]] = func(-g[i](),1); else if(rev[i] && type[i]) w[id[i]] = func(-g[i](),g[i]()); build(1,1,tot); scanf("%d",&q); for(int x;q;--q) scanf("%d",&x), rev[x] ^= 1,update(x), printf("%d\n",f[rt]), rev[x] ^= 1,update(x); fclose(stdin),fclose(stdout); return 0; }

题库

题库

3935.[CSP-J2020] 表达式

提交记录

测试用例