来源第 176 场双周赛 Q4难度困难分数2384
题目描述
给你一棵包含 n 个节点的无向树,节点编号从 0 到 n - 1。树由一个长度为 n - 1 的二维数组 edges 表示,其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 之间存在一条无向边。
另给你一个长度为 n 且由小写英文字母组成的字符串 s,其中 s[i] 表示分配给节点 i 的字符。
还给你一个字符串数组 queries,其中每个 queries[i] 为以下形式之一:
"update ui c":将节点 ui 处的字符更改为 c。正式地,更新 s[ui] = c。 "query ui vi":判断从 ui 到 vi 的 唯一 路径(含两端点)上的字符所组成的字符串,是否可以 重新排列 成一个 回文串。
返回一个布尔数组 answer,如果第 i 个类型为 "query ui vi" 的查询可以重新排列成 回文串 ,则 answer[i] 为 true,否则为 false。
回文串 是指正读和反读都相同的字符串。
示例 1:
输入: n = 3, edges = [[0,1],[1,2]], s = "aac", queries = ["query 0 2","update 1 b","query 0 2"]
输出: [true,false]
解释:
"query 0 2":路径 0 → 1 → 2 得到的字符串是 "aac",可以重新排列形成 "aca",这是一个回文串。因此,answer[0] = true。 "update 1 b":将节点 1 更新为 'b',现在 s = "abc"。 "query 0 2":路径上的字符为 "abc",无法重新排列形成回文串。因此,answer[1] = false。
因此,answer = [true, false]。
示例 2:
输入: n = 4, edges = [[0,1],[0,2],[0,3]], s = "abca", queries = ["query 1 2","update 0 b","query 2 3","update 3 a","query 1 3"]
输出: [false,false,true]
解释:
"query 1 2":路径 1 → 0 → 2 得到的字符串是 "bac",无法重新排列形成回文串。因此,answer[0] = false。 "update 0 b":将节点 0 更新为 'b',现在 s = "bbca"。 "query 2 3":路径 2 → 0 → 3 得到的字符串是 "cba",无法重新排列形成回文串。因此,answer[1] = false。 "update 3 a":将节点 3 更新为 'a',s = "bbca"。 "query 1 3":路径 1 → 0 → 3 得到的字符串是 "bba",可以重新排列形成 "bab",这是一个回文串。因此,answer[2] = true。
因此,answer = [false, false, true]。
提示:
1 <= n == s.length <= 5 * 104 edges.length == n - 1 edges[i] = [ui, vi] 0 <= ui, vi <= n - 1 s 由小写英文字母组成。 - 输入生成的
edges 表示一棵有效的树。 1 <= queries.length <= 5 * 104 queries[i] = "update ui c" 或 queries[i] = "query ui vi" 0 <= ui, vi <= n - 1 c 是一个小写英文字母。
解法
方法一:欧拉序 + 树状数组 + 倍增
思考
路径上的字符能重排成回文,当且仅当至多一个字符出现奇数次。 \(n\) 与询问数都不超过 \(5 \times 10^4\),逐条路径扫描会超时。
瓶颈是既要支持单点改字符,又要快速取出任意路径上各字母次数的奇偶。
把 \(26\) 个字母的奇偶压成位掩码后,路径掩码等于两端到根的前缀异或,再异或 LCA 上的字符:公共前缀和 LCA 本身在两个前缀里都被抵消了。欧拉序上把每个点的掩码写在进入和离开时刻,异或树状数组的前缀就是点到根的掩码。
倍增求出 LCA 后,检查路径掩码是否至多一位为 \(1\);更新只在该点的进入、离开时刻异或新旧掩码之差。
我们把每个字符出现次数的奇偶压成一个 \(26\) 位掩码:第 \(c\) 位为 \(1\) 表示字符 \(c\) 出现了奇数次。路径上的字符可以重排成回文串,当且仅当该路径掩码至多有一个二进制位为 \(1\)(含全 \(0\)),也就是掩码与自身减一的按位与等于 \(0\)。
记 \(\textit{pref}(u)\) 为从根到节点 \(u\)(含 \(u\))的掩码异或。设 \(w\) 是 \(u\) 与 \(v\) 的最近公共祖先,则 \(u\) 到 \(v\) 的路径掩码为
\[\textit{pref}(u) \oplus \textit{pref}(v) \oplus \textit{bit}[w].\]
从根到 \(w\) 的部分在两个前缀中各出现一次,异或后抵消; \(w\) 本身也被抵消,因此再异或 \(\textit{bit}[w]\),把它补回路径。
\(\textit{pref}(u)\) 用欧拉序和异或树状数组维护。深度优先遍历时,我们记录节点 \(u\) 的进入时间 \(\textit{tin}[u]\) 与离开时间 \(\textit{tout}[u]\),并把 \(\textit{bit}[u]\) 同时加到这两个位置。查询前缀到 \(\textit{tin}[u]\) 时,根到 \(u\) 上的每个节点只被计入一次:进入时刻落在前缀内,离开时刻落在前缀外;已经完整离开的子树被计入两次,异或后抵消。树状数组按下标 \(1\) 起累加,所以代码中的 \(\textit{query}(\textit{tin}[u] + 1)\) 就是 \(\textit{pref}(u)\)。
修改节点 \(u\) 的字符时,令 \(\delta\) 为旧掩码与新掩码的异或,在 \(\textit{tin}[u]\) 和 \(\textit{tout}[u]\) 上再异或 \(\delta\) 即可。最近公共祖先用倍增预处理,单次询问 \(O(\log n)\)。
时间复杂度 \(O((n + q) \log n)\),空间复杂度 \(O(n \log n)\)。其中 \(n\) 是节点数, \(q\) 是操作数。
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 | class BinaryIndexedTree:
def __init__(self, n: int):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i: int, delta: int) -> None:
i += 1
while i <= self.n:
self.tree[i] ^= delta
i += i & -i
def query(self, i: int) -> int:
res = 0
while i:
res ^= self.tree[i]
i -= i & -i
return res
class Solution:
def palindromePath(
self, n: int, edges: list[list[int]], s: str, queries: list[str]
) -> list[bool]:
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
parent = [-1] * n
depth = [0] * n
tin = [0] * n
tout = [0] * n
timer = 0
def dfs(u: int, p: int) -> None:
nonlocal timer
parent[u] = p
tin[u] = timer
timer += 1
for v in g[u]:
if v != p:
depth[v] = depth[u] + 1
dfs(v, u)
tout[u] = timer
dfs(0, -1)
m = n.bit_length()
up = [parent[:]]
up[0][0] = 0
for j in range(1, m):
prev = up[-1]
up.append([prev[prev[i]] for i in range(n)])
def lca(u: int, v: int) -> int:
if depth[u] < depth[v]:
u, v = v, u
d = depth[u] - depth[v]
j = 0
while d:
if d & 1:
u = up[j][u]
d >>= 1
j += 1
if u == v:
return u
for j in range(m - 1, -1, -1):
if up[j][u] != up[j][v]:
u = up[j][u]
v = up[j][v]
return parent[u]
bit = [1 << (ord(c) - ord("a")) for c in s]
tree = BinaryIndexedTree(n)
for u in range(n):
tree.update(tin[u], bit[u])
tree.update(tout[u], bit[u])
ans = []
for q in queries:
op, a, b = q.split()
u = int(a)
if op == "update":
x = bit[u]
y = 1 << (ord(b) - ord("a"))
if x != y:
delta = x ^ y
tree.update(tin[u], delta)
tree.update(tout[u], delta)
bit[u] = y
else:
v = int(b)
w = lca(u, v)
mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w]
ans.append(mask & (mask - 1) == 0)
return ans
|
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 | class BinaryIndexedTree {
int n;
int[] tree;
BinaryIndexedTree(int n) {
this.n = n;
tree = new int[n + 1];
}
void update(int i, int delta) {
for (i++; i <= n; i += i & -i) {
tree[i] ^= delta;
}
}
int query(int i) {
int res = 0;
for (; i > 0; i -= i & -i) {
res ^= tree[i];
}
return res;
}
}
class Solution {
List<Integer>[] g;
int[] parent, depth, tin, tout, bit;
int[][] up;
int timer, m;
public List<Boolean> palindromePath(int n, int[][] edges, String s, String[] queries) {
g = new List[n];
for (int i = 0; i < n; i++) {
g[i] = new ArrayList<>();
}
for (int[] e : edges) {
g[e[0]].add(e[1]);
g[e[1]].add(e[0]);
}
parent = new int[n];
depth = new int[n];
tin = new int[n];
tout = new int[n];
timer = 0;
dfs(0, -1);
m = 32 - Integer.numberOfLeadingZeros(n);
up = new int[m][n];
System.arraycopy(parent, 0, up[0], 0, n);
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
up[j][i] = up[j - 1][up[j - 1][i]];
}
}
bit = new int[n];
for (int i = 0; i < n; i++) {
bit[i] = 1 << (s.charAt(i) - 'a');
}
BinaryIndexedTree tree = new BinaryIndexedTree(n);
for (int i = 0; i < n; i++) {
tree.update(tin[i], bit[i]);
tree.update(tout[i], bit[i]);
}
List<Boolean> ans = new ArrayList<>();
for (String q : queries) {
String[] parts = q.split(" ");
int u = Integer.parseInt(parts[1]);
if (parts[0].equals("update")) {
int x = bit[u];
int y = 1 << (parts[2].charAt(0) - 'a');
if (x != y) {
int delta = x ^ y;
tree.update(tin[u], delta);
tree.update(tout[u], delta);
bit[u] = y;
}
} else {
int v = Integer.parseInt(parts[2]);
int w = lca(u, v);
int mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w];
ans.add((mask & (mask - 1)) == 0);
}
}
return ans;
}
void dfs(int u, int p) {
parent[u] = p == -1 ? 0 : p;
tin[u] = timer++;
for (int v : g[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
tout[u] = timer;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) {
int t = u;
u = v;
v = t;
}
int d = depth[u] - depth[v];
for (int j = 0; d > 0; j++, d >>= 1) {
if ((d & 1) != 0) {
u = up[j][u];
}
}
if (u == v) {
return u;
}
for (int j = m - 1; j >= 0; j--) {
if (up[j][u] != up[j][v]) {
u = up[j][u];
v = up[j][v];
}
}
return parent[u];
}
}
|
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 | class BinaryIndexedTree {
int n;
vector<int> tree;
public:
BinaryIndexedTree(int n)
: n(n)
, tree(n + 1) {}
void update(int i, int delta) {
for (++i; i <= n; i += i & -i) {
tree[i] ^= delta;
}
}
int query(int i) {
int res = 0;
for (; i > 0; i -= i & -i) {
res ^= tree[i];
}
return res;
}
};
class Solution {
vector<vector<int>> g, up;
vector<int> parent, depth, tin, tout, bit;
int timer, m;
void dfs(int u, int p) {
parent[u] = p == -1 ? 0 : p;
tin[u] = timer++;
for (int v : g[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
tout[u] = timer;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
int d = depth[u] - depth[v];
for (int j = 0; d; j++, d >>= 1) {
if (d & 1) {
u = up[j][u];
}
}
if (u == v) {
return u;
}
for (int j = m - 1; j >= 0; j--) {
if (up[j][u] != up[j][v]) {
u = up[j][u];
v = up[j][v];
}
}
return parent[u];
}
public:
vector<bool> palindromePath(int n, vector<vector<int>>& edges, string s, vector<string>& queries) {
g.assign(n, {});
for (auto& e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
parent.resize(n);
depth.assign(n, 0);
tin.resize(n);
tout.resize(n);
timer = 0;
dfs(0, -1);
m = 32 - __builtin_clz(n);
up.assign(m, vector<int>(n));
up[0] = parent;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
up[j][i] = up[j - 1][up[j - 1][i]];
}
}
bit.resize(n);
for (int i = 0; i < n; i++) {
bit[i] = 1 << (s[i] - 'a');
}
BinaryIndexedTree tree(n);
for (int i = 0; i < n; i++) {
tree.update(tin[i], bit[i]);
tree.update(tout[i], bit[i]);
}
vector<bool> ans;
for (string& q : queries) {
stringstream ss(q);
string op;
int u;
ss >> op >> u;
if (op == "update") {
string c;
ss >> c;
int y = 1 << (c[0] - 'a');
if (bit[u] != y) {
int delta = bit[u] ^ y;
tree.update(tin[u], delta);
tree.update(tout[u], delta);
bit[u] = y;
}
} else {
int v;
ss >> v;
int w = lca(u, v);
int mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w];
ans.push_back((mask & (mask - 1)) == 0);
}
}
return ans;
}
};
|
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 | type BinaryIndexedTree struct {
n int
tree []int
}
func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
return &BinaryIndexedTree{n: n, tree: make([]int, n+1)}
}
func (b *BinaryIndexedTree) update(i, delta int) {
for i++; i <= b.n; i += i & -i {
b.tree[i] ^= delta
}
}
func (b *BinaryIndexedTree) query(i int) int {
res := 0
for ; i > 0; i -= i & -i {
res ^= b.tree[i]
}
return res
}
func palindromePath(n int, edges [][]int, s string, queries []string) []bool {
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
parent := make([]int, n)
depth := make([]int, n)
tin := make([]int, n)
tout := make([]int, n)
timer := 0
var dfs func(int, int)
dfs = func(u, p int) {
if p == -1 {
parent[u] = 0
} else {
parent[u] = p
}
tin[u] = timer
timer++
for _, v := range g[u] {
if v != p {
depth[v] = depth[u] + 1
dfs(v, u)
}
}
tout[u] = timer
}
dfs(0, -1)
m := 1
for (1 << m) <= n {
m++
}
up := make([][]int, m)
up[0] = append([]int(nil), parent...)
for j := 1; j < m; j++ {
up[j] = make([]int, n)
for i := 0; i < n; i++ {
up[j][i] = up[j-1][up[j-1][i]]
}
}
bit := make([]int, n)
for i := 0; i < n; i++ {
bit[i] = 1 << (s[i] - 'a')
}
tree := NewBinaryIndexedTree(n)
for i := 0; i < n; i++ {
tree.update(tin[i], bit[i])
tree.update(tout[i], bit[i])
}
lca := func(u, v int) int {
if depth[u] < depth[v] {
u, v = v, u
}
d := depth[u] - depth[v]
for j := 0; d > 0; j++ {
if d&1 != 0 {
u = up[j][u]
}
d >>= 1
}
if u == v {
return u
}
for j := m - 1; j >= 0; j-- {
if up[j][u] != up[j][v] {
u = up[j][u]
v = up[j][v]
}
}
return parent[u]
}
ans := make([]bool, 0)
for _, q := range queries {
var op string
var u int
fmt.Sscanf(q, "%s %d", &op, &u)
if op == "update" {
var c string
fmt.Sscanf(q, "%s %d %s", &op, &u, &c)
y := 1 << (c[0] - 'a')
if bit[u] != y {
delta := bit[u] ^ y
tree.update(tin[u], delta)
tree.update(tout[u], delta)
bit[u] = y
}
} else {
var v int
fmt.Sscanf(q, "%s %d %d", &op, &u, &v)
w := lca(u, v)
mask := tree.query(tin[u]+1) ^ tree.query(tin[v]+1) ^ bit[w]
ans = append(ans, mask&(mask-1) == 0)
}
}
return ans
}
|
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 | class BinaryIndexedTree {
n: number;
tree: number[];
constructor(n: number) {
this.n = n;
this.tree = Array(n + 1).fill(0);
}
update(i: number, delta: number): void {
for (i++; i <= this.n; i += i & -i) {
this.tree[i] ^= delta;
}
}
query(i: number): number {
let res = 0;
for (; i > 0; i -= i & -i) {
res ^= this.tree[i];
}
return res;
}
}
function palindromePath(n: number, edges: number[][], s: string, queries: string[]): boolean[] {
const g: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const parent = Array(n).fill(0);
const depth = Array(n).fill(0);
const tin = Array(n).fill(0);
const tout = Array(n).fill(0);
let timer = 0;
function dfs(u: number, p: number): void {
parent[u] = p === -1 ? 0 : p;
tin[u] = timer++;
for (const v of g[u]) {
if (v !== p) {
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
tout[u] = timer;
}
dfs(0, -1);
const m = 32 - Math.clz32(n);
const up: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
up[0] = [...parent];
for (let j = 1; j < m; j++) {
for (let i = 0; i < n; i++) {
up[j][i] = up[j - 1][up[j - 1][i]];
}
}
const bit = Array(n).fill(0);
for (let i = 0; i < n; i++) {
bit[i] = 1 << (s.charCodeAt(i) - 97);
}
const tree = new BinaryIndexedTree(n);
for (let i = 0; i < n; i++) {
tree.update(tin[i], bit[i]);
tree.update(tout[i], bit[i]);
}
function lca(u: number, v: number): number {
if (depth[u] < depth[v]) {
[u, v] = [v, u];
}
let d = depth[u] - depth[v];
for (let j = 0; d > 0; j++, d >>= 1) {
if (d & 1) {
u = up[j][u];
}
}
if (u === v) {
return u;
}
for (let j = m - 1; j >= 0; j--) {
if (up[j][u] !== up[j][v]) {
u = up[j][u];
v = up[j][v];
}
}
return parent[u];
}
const ans: boolean[] = [];
for (const q of queries) {
const parts = q.split(' ');
const u = Number(parts[1]);
if (parts[0] === 'update') {
const y = 1 << (parts[2].charCodeAt(0) - 97);
if (bit[u] !== y) {
const delta = bit[u] ^ y;
tree.update(tin[u], delta);
tree.update(tout[u], delta);
bit[u] = y;
}
} else {
const v = Number(parts[2]);
const w = lca(u, v);
const mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w];
ans.push((mask & (mask - 1)) === 0);
}
}
return ans;
}
|
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
152
153
154 | struct BinaryIndexedTree {
n: usize,
tree: Vec<i32>,
}
impl BinaryIndexedTree {
fn new(n: usize) -> Self {
Self {
n,
tree: vec![0; n + 1],
}
}
fn update(&mut self, mut i: usize, delta: i32) {
i += 1;
while i <= self.n {
self.tree[i] ^= delta;
i += i & i.wrapping_neg();
}
}
fn query(&self, mut i: usize) -> i32 {
let mut res = 0;
while i > 0 {
res ^= self.tree[i];
i -= i & i.wrapping_neg();
}
res
}
}
impl Solution {
pub fn palindrome_path(
n: i32,
edges: Vec<Vec<i32>>,
s: String,
queries: Vec<String>,
) -> Vec<bool> {
let n = n as usize;
let mut g = vec![vec![]; n];
for e in &edges {
let u = e[0] as usize;
let v = e[1] as usize;
g[u].push(v);
g[v].push(u);
}
let mut parent = vec![0usize; n];
let mut depth = vec![0usize; n];
let mut tin = vec![0usize; n];
let mut tout = vec![0usize; n];
let mut timer = 0usize;
fn dfs(
u: usize,
p: usize,
g: &[Vec<usize>],
parent: &mut [usize],
depth: &mut [usize],
tin: &mut [usize],
tout: &mut [usize],
timer: &mut usize,
) {
parent[u] = if p == usize::MAX { 0 } else { p };
tin[u] = *timer;
*timer += 1;
for &v in &g[u] {
if v != p {
depth[v] = depth[u] + 1;
dfs(v, u, g, parent, depth, tin, tout, timer);
}
}
tout[u] = *timer;
}
dfs(
0,
usize::MAX,
&g,
&mut parent,
&mut depth,
&mut tin,
&mut tout,
&mut timer,
);
let m = (32 - (n as u32).leading_zeros()) as usize;
let mut up = vec![vec![0usize; n]; m];
up[0].clone_from(&parent);
for j in 1..m {
for i in 0..n {
up[j][i] = up[j - 1][up[j - 1][i]];
}
}
let lca = |mut u: usize, mut v: usize| -> usize {
if depth[u] < depth[v] {
std::mem::swap(&mut u, &mut v);
}
let mut d = depth[u] - depth[v];
let mut j = 0;
while d > 0 {
if d & 1 == 1 {
u = up[j][u];
}
d >>= 1;
j += 1;
}
if u == v {
return u;
}
for j in (0..m).rev() {
if up[j][u] != up[j][v] {
u = up[j][u];
v = up[j][v];
}
}
parent[u]
};
let bytes = s.as_bytes();
let mut bit = vec![0i32; n];
for i in 0..n {
bit[i] = 1 << (bytes[i] - b'a') as u32;
}
let mut tree = BinaryIndexedTree::new(n);
for i in 0..n {
tree.update(tin[i], bit[i]);
tree.update(tout[i], bit[i]);
}
let mut ans = Vec::new();
for q in &queries {
let parts: Vec<&str> = q.split(' ').collect();
let u: usize = parts[1].parse().unwrap();
if parts[0] == "update" {
let x = bit[u];
let y = 1 << (parts[2].as_bytes()[0] - b'a') as u32;
if x != y {
let delta = x ^ y;
tree.update(tin[u], delta);
tree.update(tout[u], delta);
bit[u] = y;
}
} else {
let v: usize = parts[2].parse().unwrap();
let w = lca(u, v);
let mask = tree.query(tin[u] + 1) ^ tree.query(tin[v] + 1) ^ bit[w];
ans.push(mask & (mask - 1) == 0);
}
}
ans
}
}
|