洛谷P7073 表达式 题解

发表于 | 分类于

题意：
给定一个含有一些0/1变量的后缀表达式，每次询问临时将一个变量的值取反，求此时表达式的值。

分享一个题解区没有的 $O((n+q)\log n)$ 的倍增做法。

首先建立出表达式树。

然后修改一个位置的数的时候，我们发现只会影响它到根节点的路径上的数值，而不会影响到其它节点的数值。

暴力修改太耗时了，于是我们想到了这道题。

考虑倍增。

设 $f_{i,j,k}$ 为第 $i$ 个节点取值为 $k$ 时向上跳 $2^j$ 步后的节点的数值，那么：

${f_{i,j,k}=f_{anc_{j,i-1},j-1,f_{i,j-1,k}}}$，

其中 $anc_{i,j}$ 为第 $i$ 个节点向上跳 $2^j$ 步的节点。

解释一下就是先向上跳 $2^{j-1}$ 步过后，到达 $anc_{i,j-1}$ ，它上面的数值是 $f_{i,j-1,k}$。

再在 $anc_{i,j-1}$ 的取值为 $f_{i,j-1,k}$ 的基础上向上跳 $2^{j-1}$ 步，就是 ${f_{i,j,k}=f_{anc_{j,i-1},j-1,f_{i,j-1,k}}}$ 了。

查询的时候把 $x_i$ 的取值取反，然后倍增跳到根节点，最后根节点的数值就是表达式的值。

就 AC 了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

struct node {
	int lson, rson, fa, mark, op;
} t[maxn << 2];

int cnt, n, m, a[maxn], anc[maxn << 2][20], f[maxn << 2][20][2], root, pos[maxn];
int depth[maxn << 2], qwq[maxn << 2][2], g[maxn << 2]; 

char c[maxn];

stack < int > st;

void dfs(int x) {
	depth[x] = depth[t[x].fa] + 1;
	if(t[x].lson) {
		dfs(t[x].lson);
		dfs(t[x].rson);
		if(t[x].op == 1) {
			g[x] = g[t[x].lson] & g[t[x].rson];
		}
		if(t[x].op == 2) {
			g[x] = g[t[x].lson] | g[t[x].rson];
		}
	}
	if(t[x].mark) g[x] = 1 - g[x];
}

inline int up(int x) {
	int val = 1 - g[pos[x]], p = pos[x];
	for(register int i = 18; i >= 0; i--) {
		if(anc[p][i] ^ root) {
			val = f[p][i][val];
			p = anc[p][i];
		}
	}
	return f[p][0][val];
}

int main() {
	while(1) {
		scanf("%s", c);
		if(c[0] == 'x') {
			int x; sscanf(c + 1, "%d", &x);
			pos[x] = ++cnt;
			st.push(cnt);
		}
		if(c[0] == '!') {
			int k = st.top();
			t[k].mark = 1 - t[k].mark;
		}
		if(c[0] == '&') {
			int b = st.top(); st.pop();
			int a = st.top(); st.pop();
			t[a].fa = t[b].fa = ++cnt;
			t[cnt].lson = a, t[cnt].rson = b;
			t[cnt].op = 1;
			st.push(cnt);
		}
		if(c[0] == '|') {
			int b = st.top(); st.pop();
			int a = st.top(); st.pop();
			t[a].fa = t[b].fa = ++cnt;
			t[cnt].lson = a, t[cnt].rson = b;
			t[cnt].op = 2;
			st.push(cnt);
		}
		if(c[0] >= '0' && c[0] <= '9') {
			sscanf(c, "%d", &n); 
			break ;
		}
	}
	root = st.top();
	for(register int i = 1; i <= n; i++) scanf("%d", &a[i]), g[pos[i]] = a[i];
	dfs(root);
	for(register int i = 1; i <= cnt; i++) {
		anc[i][0] = t[i].fa;
		if(t[t[i].fa].lson == i) {
			if(t[t[i].fa].op == 1) {
				f[i][0][0] = 0;
				f[i][0][1] = g[t[t[i].fa].rson];
			}
			if(t[t[i].fa].op == 2) {
				f[i][0][0] = g[t[t[i].fa].rson];
				f[i][0][1] = 1;
			}
		} else {
			if(t[t[i].fa].op == 1) {
				f[i][0][0] = 0;
				f[i][0][1] = g[t[t[i].fa].lson];
			}
			if(t[t[i].fa].op == 2) {
				f[i][0][0] = g[t[t[i].fa].lson];
				f[i][0][1] = 1;
			}
		} 
		if(t[t[i].fa].mark) f[i][0][0] = 1 - f[i][0][0], f[i][0][1] = 1 - f[i][0][1];
	}
	anc[root][0] = root;
	for(register int i = 1; i <= 18; i++) {
		for(register int j = 1; j <= cnt; j++) {
			anc[j][i] = anc[anc[j][i - 1]][i - 1];
			f[j][i][0] = f[anc[j][i - 1]][i - 1][f[j][i - 1][0]];
			f[j][i][1] = f[anc[j][i - 1]][i - 1][f[j][i - 1][1]];
		}
	}
	scanf("%d", &m);
	while(m--) {
		int x; scanf("%d", &x);
		printf("%d\n", up(x));
	}
	return 0;
}