zqs`s blog

有朋自远方来，虽远必诛

题解 【P5354 [Ynoi2017] 由乃的 OJ】

发表于 分类于 Valine：

这题的确是那道起床困难综合症的树上带修。

那先回忆起床困难综合症怎么做：

由于位运算对于每一位是独立的，所以把每一位分开考虑，算出每一位取 $0/1$ 后，操作完后这一位是 $0$ 还是 $1$。

然后贪心，从高到低考虑每一位，如果这一位取 $1$ 操作完成后比取 $0$ 操作完成后的值大，并且这一位取 $1$ 不会超出限制，那么这一位取 $1$，否则取 $0$。

搬到了树上比较好解决，直接树剖压成链就好了。

带修可以想到线段树维护，对于线段树每一个管辖区间 $[l,r]$ 的节点，都维护第 $k$ 位（$0\le k\le 63$）取 $0/1$，从 $l$ 到 $r$ 经过所有操作后，第 $k$ 位是 $0$ 还是 $1$，再维护从 $r$ 到 $l$ 经过所有操作后，第 $k$ 位是 $0$ 还是 $1$。

对于每个线段树节点都维护一下四个数组：

$lv0_k$ 表示第 $k$ 位取 $0$ 从 $l$ 到 $r$ 经过所有操作后第 $k$ 位的值；
$lv1_k$ 表示第 $k$ 位取 $1$ 从 $l$ 到 $r$ 经过所有操作后第 $k$ 位的值;
$rv0_k$ 表示第 $k$ 位取 $0$ 从 $r$ 到 $l$ 经过所有操作后第 $k$ 位的值；
$lv1_k$ 表示第 $k$ 位取 $1$ 从 $r$ 到 $l$ 经过所有操作后第 $k$ 位的值。

合并不再赘述。

那这样的时间复杂度是 $O(nk\log^2 n)$ 的，显然过不了。

我们发现，$lv0,lv1,rv0,rv1$ 虽然是一个数组，但每一位只有 $0/1$ 两种可能，因此我们考虑像 bitset 压位一样，把这四个数组压回一个unsigned long long里。

压位过后，考虑如何在线段树上快速 $O(1)$ 而非 $O(k)$ 合并。

直接扔式子：

1
2
3
4
tree[O].lv0 = (ls.lv0 & rs.lv1) | (~ls.lv0 & rs.lv0);
tree[O].lv1 = (ls.lv1 & rs.lv1) | (~ls.lv1 & rs.lv0);
tree[O].rv0 = (rs.rv0 & ls.rv1) | (~rs.rv0 & ls.rv0)
tree[O].rv1 = (rs.rv1 & ls.rv1) | (~rs.rv1 & ls.rv0);

tree[O]就是当前的线段树节点，ls是它的左儿子，rs是它的右儿子。

关于原理，这里仅举 tree[O].lv0 一例：

由于是从左到右的，所以肯定先要经过左子树（ls.lv0）。
然后如果经过左子树后第 $k$ 位为 $1$，那么我就要看以第 $k$ 为 $1$ 为初始值经过右子树后值是多少；如果经过左子树后第 $k$ 位为 $0$，那么我就要看以第 $k$ 为 $0$ 为初始值经过右子树后值是多少。

代码巨恶心，写一天调一年。

我的代码校内OJ，洛谷，黑暗爆炸均AC，但是调试时本地测黑暗爆炸的数据时炸了，就很神奇，而且我AC代码只是把WA代码#define int unsigned long long换成了手动开unsigned long long。

代码
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <cstdio>
#include <stack>
#define ls tree[O << 1]
#define rs tree[O << 1 | 1]

typedef unsigned long long ull;
const ull MAXULL = 18446744073709551615ull;
struct Edge {
	int to, nxt;
} e[200005];
int In[100005], son[100005], sze[100005], top[100005], fa[100005], cnt, tot;
int dep[100005], head[100005], opt[100005], id[100005], n, m, k;
ull val[100005];
struct Node {
	int l, r;
	ull lv0, lv1, rv0, rv1;
} tree[400005];
struct Data {
	ull lv0, lv1, rv0, rv1;
	Data(ull lv0 = 0ull, ull lv1 = 0ull, ull rv0 = 0ull, ull rv1 = 0ull):
		lv0(lv0), lv1(lv1), rv0(rv0), rv1(rv1){}
	inline void operator = (const Data a) {
		lv0 = a.lv0, lv1 = a.lv1, rv0 = a.rv0, rv1 = a.rv1;
	}
};
std::stack<Data> s;
inline void AddEdge(int u, int v) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
}
void dfs1(int u) {
	sze[u] = 1, dep[u] = dep[fa[u]] + 1;
	for (int i = head[u]; i; i = e[i].nxt) if (e[i].to != fa[u]) {
		int v = e[i].to;
		fa[v] = u, dfs1(v), sze[u] += sze[v];
		if (sze[v] > sze[son[u]]) son[u] = v;
	}
}
void dfs2(int u) {
	id[In[u] = ++ cnt] = u;
	if (son[u]) top[son[u]] = top[u], dfs2(son[u]);
	for (int i = head[u]; i; i = e[i].nxt)
		if (e[i].to != fa[u] && e[i].to != son[u]) top[e[i].to] = e[i].to, dfs2(e[i].to);
}

inline void pushup(int O) {
	tree[O].lv0 = (ls.lv0 & rs.lv1) | (~ls.lv0 & rs.lv0);
	tree[O].lv1 = (ls.lv1 & rs.lv1) | (~ls.lv1 & rs.lv0);
	tree[O].rv0 = (rs.rv0 & ls.rv1) | (~rs.rv0 & ls.rv0);
	tree[O].rv1 = (rs.rv1 & ls.rv1) | (~rs.rv1 & ls.rv0);
}
inline void calcleaf(int O) {
	int x = id[tree[O].l];
	if (opt[x] == 1)
		tree[O].lv0 = tree[O].rv0 = 0, tree[O].lv1 = tree[O].rv1 = val[x];
	else if (opt[x] == 2)
		tree[O].lv0 = tree[O].rv0 = val[x], tree[O].lv1 = tree[O].rv1 = MAXULL;
	else tree[O].lv0 = tree[O].rv0 = val[x], tree[O].lv1 = tree[O].rv1 = ~val[x];
}
void make_tree(int O, int L, int R) {
	tree[O].l = L, tree[O].r = R;
	if (tree[O].l != tree[O].r) {
		make_tree(O << 1, L, L + R >> 1);
		make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
		pushup(O);
	} else calcleaf(O);
}
void update(int O, int p, int nopt, ull nval) {
	if (tree[O].l == tree[O].r) {
		opt[id[tree[O].l]] = nopt, val[id[tree[O].l]] = nval, calcleaf(O);
		return;
	}
	int mid = tree[O].l + tree[O].r >> 1;
	if (p <= mid) update(O << 1, p, nopt, nval);
	else update(O << 1 | 1, p, nopt, nval);
	pushup(O);
}
Data query(int O, int L, int R) {
	if (L > R) return Data(0, MAXULL, 0, MAXULL);
	if (L <= tree[O].l && tree[O].r <= R)
		return Data(tree[O].lv0, tree[O].lv1, tree[O].rv0, tree[O].rv1);
	int mid = tree[O].l + tree[O].r >> 1;
	if (R <= mid) return query(O << 1, L, R);
	if (mid < L) return query(O << 1 | 1, L, R);
	Data Ls = query(O << 1, L, R), Rs = query(O << 1 | 1, L, R), ans;
	ans.lv0 = (Ls.lv0 & Rs.lv1) | (~Ls.lv0 & Rs.lv0);
	ans.lv1 = (Ls.lv1 & Rs.lv1) | (~Ls.lv1 & Rs.lv0);
	ans.rv0 = (Rs.rv0 & Ls.rv1) | (~Rs.rv0 & Ls.rv0);
	ans.rv1 = (Rs.rv1 & Ls.rv1) | (~Rs.rv1 & Ls.rv0);
	return ans;
}

int LCA(int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) u ^= v ^= u ^= v;
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}
int getson(int lca, int u) {
	int lst = u;
	while (top[u] != top[lca]) lst = top[u], u = fa[top[u]];
	return u == lca ? lst : son[lca];
}
ull Query(int u, int v, ull lim) {
	int lca = LCA(u, v), y = getson(lca, v);//y为lca在v方向的儿子
	ull ans0 = 0ull, ans1 = MAXULL, ans = 0ull;
   //ans0存每一位取0经过u->v的路径后每一位最终结果，ans1存每一位取1经过u->v的路径后每一位最终结果，合并同线段树
	Data tmp;
	while (top[u] != top[lca]) {
		tmp = query(1, In[top[u]], In[u]);
		ans0 = (ans0 & tmp.rv1) | (~ans0 & tmp.rv0);
		ans1 = (ans1 & tmp.rv1) | (~ans1 & tmp.rv0);
		u = fa[top[u]];
	}
	tmp = query(1, In[lca], In[u]);
	ans0 = (ans0 & tmp.rv1) | (~ans0 & tmp.rv0);
	ans1 = (ans1 & tmp.rv1) | (~ans1 & tmp.rv0);
	if (v != lca) {
		while (top[v] != top[y]) s.push(query(1, In[top[v]], In[v])), v = fa[top[v]];
        	//注意树剖跳的是v->y，但我们的路径实际上是u->lca->y->v，所以这里是反着的，要用一个stack来存
		s.push(query(1, In[y], In[v]));
	}
	while (s.size()) {
		ans0 = (ans0 & s.top().lv1) | (~ans0 & s.top().lv0);
		ans1 = (ans1 & s.top().lv1) | (~ans1 & s.top().lv0);
		s.pop();
	}
	ull now = lim;
	for (int i = k - 1; i >= 0; -- i)//贪心
		if ((ans1 & 1ull << i) > (ans0 & 1ull << i) && now >= 1ull << i)
			ans += 1ull << i, now -= 1ull << i;
		else ans += ans0 & 1ull << i;
	return ans;
}

signed main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; ++ i) scanf("%d%llu", opt + i, val + i);
	for (int i = 1, u, v; i < n; ++ i)
		scanf("%d%d", &u, &v), AddEdge(u, v), AddEdge(v, u);
	dfs1(1), top[1] = 1, dfs2(1);
	make_tree(1, 1, n);
	while (m --) {
		int type, x, y;
		ull z;
		scanf("%d%d%d%llu", &type, &x, &y, &z);
		if (type == 1) printf("%llu\n", Query(x, y, z));
		else update(1, In[x], y, z);
	}
	return 0;
}
-------------本文结束感谢您的阅读-------------