应该有这种情况:!!!!!!!!!!!a
但是这份代码并没有考虑到,虽然是暴力,但是仍然没有 WA
如果剩下 TLE 的数据中有这种情况,望告知,然后我自裁
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
const int N = 100001;
const int L = 1000001;
// -1 & // -2 | // -3 !
// 0 \n
inline int readx() {
int x = 0; char ch = getchar();
while(ch != 'x' && ch != '&' && ch != '|' && ch != '!' && ch != '\n') ch = getchar();
if(ch == '\n') return 0;
if(ch == '&') return -1;
if(ch == '|') return -2;
if(ch == '!') return -3;
ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x;
}
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0') { if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
return x * f;
}
int n,map[N],st[N],tot;
int s[L],rev[L],lc[L],rc[L],fa[L],cnt;
int res[L];
void Dfs(int x) {
if(!lc[x] && !rc[x]) return void(res[x] = s[x] ^ rev[x]);
Dfs(lc[x]), Dfs(rc[x]);
if(s[x] == -1) res[x] = res[lc[x]] & res[rc[x]];
if(s[x] == -2) res[x] = res[lc[x]] | res[rc[x]];
if(rev[x] == 1) res[x] ^= 1;
// std::printf("%d ",res[x]);
}
void Change(int x) {
res[map[x]] ^= 1;
int p = fa[map[x]];
while(p != st[tot]) {
if(s[p] == -1) res[p] = res[lc[p]] & res[rc[p]];
if(s[p] == -2) res[p] = res[lc[p]] | res[rc[p]];
if(rev[p] == 1) res[p] ^= 1;
p = fa[p];
}
if(s[p] == -1) res[p] = res[lc[p]] & res[rc[p]];
if(s[p] == -2) res[p] = res[lc[p]] | res[rc[p]];
if(rev[p] == 1) res[p] ^= 1;
return;
}
int main() {
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
int x;
while(true) {
x = readx();
if(!x) break;
if(x > 0) {
st[++tot] = map[x] = ++cnt;
} else if(x == -3) {
rev[st[tot]] = true;
} else {
int b = st[tot--];
int a = st[tot--];
s[++cnt] = x;
lc[cnt] = a, rc[cnt] = b;
fa[a] = cnt, fa[b] = cnt;
st[++tot] = cnt;
}
}
n = read();
for(int i = 1;i <= n;i++) s[map[i]] = read();
Dfs(st[tot]);
int q = read();
while(q--) {
int x = read();
Change(x);
std::printf("%d\n",res[st[tot]]);
Change(x);
}
// std::puts("");
return 0;
}