[EZOI][1225NOI模拟赛]farmer(树链剖分+线段树)

§ 1 题意

给定一棵有 $n$ 个节点二叉树的第 $i$ 个节点的权值 $a_i$ 以及左右儿子编号(若不存在则为 $0$)。

给出 $m$ 次操作,每次操作均为以下 $3$ 种之一:

  • $1\ u\ v$:将节点 $u$ 的权值修改为 $v$。
  • $2\ u$:将节点 $u$ 及其子树内所有点的左右儿子交换。
  • $3\ u$:询问从根开始走,若当前节点权值小于 $a_u$ 则向左儿子走,大于 $a_u$ 则向右儿子走,等于 $a_u$ 则停止,若能走到 $u$ 点则输出 YES,否则输出 NO

$1\leq n,m\leq 10^5,\ \ 1\leq a_i,v\leq 10^9,\ \ 1\leq u\leq n$。


§ 2 分析

若不存在操作 $2$,容易发现一个节点 $u$ 可以被走到,当且仅当从根节点到它的路径上,向右儿子走的节点中的最大权值严格小于 $a_u$,且向左儿子走的节点中的最小权值严格大于 $a_u$。

考虑用树剖维护根到每个节点的路径上向右儿子走的节点的最大权值,以及向左儿子走的节点中的最小权值即可。

而子树翻转操作相当于将两个限制符号取反,所以再维护取反后的信息,子树翻转时交换并打标记即可。

总时间复杂度为 $O(m\log^2n)$。


§ 3 代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 100005
#define inf 0x3f3f3f3f
using namespace std;
typedef struct {int mx, mn;} Pair;

inline void getint(int &num){
register int ch, neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch & 15;
while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
if(neg) num = -num;
}

int n, m, a[100005], fa[100005], ch[100005][2], root;
int siz[100005], seni[100005], dfn[100005], dout[100005], dfstime = 0, id[100005], top[100005];
int mx[400005][2], mn[400005][2], rev[400005];
#define lch (u << 1)
#define rch (u << 1 | 1)

inline void update(const int &u){
mx[u][0] = max(mx[lch][0], mx[rch][0]);
mx[u][1] = max(mx[lch][1], mx[rch][1]);
mn[u][0] = min(mn[lch][0], mn[rch][0]);
mn[u][1] = min(mn[lch][1], mn[rch][1]);
}

inline void pushdown(const int &u){
if(!rev[u]) return;
swap(mx[lch][0], mx[lch][1]), swap(mx[rch][0], mx[rch][1]);
swap(mn[lch][0], mn[lch][1]), swap(mn[rch][0], mn[rch][1]);
rev[lch] ^= 1, rev[rch] ^= 1, rev[u] = 0;
}

void build(const int &u, const int &l, const int &r){
if(l == r){
mx[u][0] = mx[u][1] = -inf, mn[u][0] = mn[u][1] = inf;
const int &dir = seni[id[l]];
if(~dir) mx[u][dir] = mn[u][dir] = a[fa[id[l]]];
return;
}
const int mid = l + r >> 1;
build(lch, l, mid), build(rch, mid + 1, r), update(u);
}

void modify(const int &u, const int &l, const int &r, const int &p, const int &v){
if(l == r){
mx[u][0] = mx[u][1] = -inf, mn[u][0] = mn[u][1] = inf;
const int &dir = seni[id[l]];
if(~dir) mx[u][dir] = mn[u][dir] = v;
if(rev[u]) swap(mx[u][0], mx[u][1]), swap(mn[u][0], mn[u][1]);
return;
}
const int mid = l + r >> 1;
pushdown(u);
if(p <= mid) modify(lch, l, mid, p, v);
else modify(rch, mid + 1, r, p, v);
update(u);
}

void rever(const int &u, const int &l, const int &r, const int &L, const int &R){
if(l == L && r == R){
swap(mx[u][0], mx[u][1]), swap(mn[u][0], mn[u][1]), rev[u] ^= 1;
return;
}
const int mid = l + r >> 1;
pushdown(u);
if(R <= mid) rever(lch, l, mid, L, R);
else if(L > mid) rever(rch, mid + 1, r, L, R);
else rever(lch, l, mid, L, mid), rever(rch, mid + 1, r, mid + 1, R);
update(u);
}

Pair query(const int &u, const int &l, const int &r, const int &L, const int &R){
if(l == L && r == R) return (Pair){mx[u][1], mn[u][0]};
const int mid = l + r >> 1;
pushdown(u);
if(R <= mid) return query(lch, l, mid, L, R);
if(L > mid) return query(rch, mid + 1, r, L, R);
const Pair lp = query(lch, l, mid, L, mid), rp = query(rch, mid + 1, r, mid + 1, R);
return (Pair){max(lp.mx, rp.mx), min(lp.mn, rp.mn)};
}

void dfs1(const int &u){
siz[u] = 1;
for(register int i = 0; i <= 1; i++)
if(ch[u][i]) seni[ch[u][i]] = i, dfs1(ch[u][i]), siz[u] += siz[ch[u][i]];
}

void dfs2(const int &u){
dfn[u] = ++dfstime, id[dfstime] = u; int hson = 0;
for(register int i = 0; i <= 1; i++) if(siz[ch[u][i]] > siz[hson]) hson = ch[u][i];
if(hson) top[hson] = top[u], dfs2(hson); // Don't return, in order to calc dout[u]
for(register int i = 0; i <= 1; i++) if(ch[u][i] && ch[u][i] != hson) top[ch[u][i]] = ch[u][i], dfs2(ch[u][i]);
dout[u] = dfstime;
}

inline Pair query(int u){
register Pair res = (Pair){-inf, inf}, cur;
while(u){
cur = query(1, 1, n, dfn[top[u]], dfn[u]);
res = (Pair){max(res.mx, cur.mx), min(res.mn, cur.mn)};
u = fa[top[u]];
}
return res;
}

int main(){
getint(n), getint(m), memset(seni, 0xff, sizeof(seni));
for(register int i = 1; i <= n; i++){
getint(a[i]), getint(ch[i][0]), getint(ch[i][1]);
fa[ch[i][0]] = fa[ch[i][1]] = i;
}
fa[0] = 0;
for(register int i = 1; i <= n; i++) if(!fa[i]) {root = i; break;}
dfs1(root), top[root] = root, dfs2(root), build(1, 1, n);
while(m--){
int opt, u, v; getint(opt), getint(u);
if(opt == 1){
getint(v), a[u] = v;
if(ch[u][0]) modify(1, 1, n, dfn[ch[u][0]], v);
if(ch[u][1]) modify(1, 1, n, dfn[ch[u][1]], v);
}
else if(opt == 2){
if(dfn[u] >= dout[u]) continue;
rever(1, 1, n, dfn[u] + 1, dout[u]);
}
else{
register Pair res = query(u);
puts(a[u] > res.mx && a[u] < res.mn ? "YES" : "NO");
}
}
return 0;
}