题解 CF343D Water Tree

似乎莫得人是不用树剖的w

但是为什么的一只log\log乱搞被树剖的两只log\log爆踩啊

是因为我实现的太丑了吗

不管了直接讲做法好了

首先,我们考虑一个很显然的结论:

如果我们对于节点xx他上次被灌水的时间位xx,上次被清除水的时间是yy

那么若有x>yx > y则此时这个节点有水

否则这个节点没水

然后我们再考虑如何维护xxyy​

我们把两种修改分别讨论,分别用树上差分和dfsdfs序维护,就可以愉快地以O(nlogn)O(n \log n)的复杂度切掉此题。

代码

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
#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647
#define lc(a) (a << 1)
#define rc(a) (a << 1 | 1)

int inp(){
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}

struct SEG_Tree{
struct SEG{
int l;
int r;
int max;
int lazy;
}t[2000000];

void push_up(int cur){
t[cur].max = std::max(t[lc(cur)].max, t[rc(cur)].max);
}

void push_down(int cur){
if(!t[cur].lazy)
return ;
t[lc(cur)].max = t[rc(cur)].max = t[lc(cur)].lazy = t[rc(cur)].lazy = t[cur].lazy;
t[cur].lazy = 0;
}

void build(int cur, int l, int r){
t[cur].l = l;
t[cur].r = r;
t[cur].max = 0;
t[cur].lazy = 0;
if(l == r)
return ;
int mid = (l + r) >> 1;
build(lc(cur), l, mid);
build(rc(cur), mid + 1, r);
}

void modify(int cur, int l, int r, int c){
if(t[cur].l > r || t[cur].r < l)
return ;
if(t[cur].l >= l && t[cur].r <= r){
t[cur].max = c;
t[cur].lazy = c;
return ;
}
push_down(cur);
modify(lc(cur), l, r, c);
modify(rc(cur), l, r, c);
push_up(cur);
}

int query(int cur, int l, int r){
if(t[cur].l > r || t[cur].r < l)
return 0;
if(t[cur].l >= l && t[cur].r <= r)
return t[cur].max;
push_down(cur);
return std::max(query(lc(cur), l, r), query(rc(cur), l, r));
}
}t1, t2;
int dfn[500010], size[500010], head[500010], nxt[1000010], end[1000010];
int cou = 0;
void link(int a, int b){
nxt[++cou] = head[a];
head[a] = cou;
end[cou] = b;
}

int idx = 0;
void dfs(int cur, int last){
dfn[cur] = ++idx;
size[cur] = 1;
for(int x = head[cur]; x != -1; x = nxt[x])
if(end[x] != last){
dfs(end[x], cur);
size[cur] += size[end[x]];
}
}

int main(){
memset(head, -1, sizeof(head));
int n = inp();
for(int i = 1; i < n; i++){
int u = inp();
int v = inp();
link(u, v);
link(v, u);
}
int m = inp();
dfs(1, 0);
t1.build(1, 1, n);
t2.build(1, 1, n);
for(int i = 1; i <= m; i++){
int op = inp();
if(op == 1){
int x = inp();
t1.modify(1, dfn[x], dfn[x] + size[x] - 1, i);
} else if(op == 2){
int x = inp();
t2.modify(1, dfn[x], dfn[x], i);
} else {
int x = inp();
int a1 = t1.query(1, dfn[x], dfn[x]);
int a2 = t2.query(1, dfn[x], dfn[x] + size[x] - 1);
// printf("%d %d\n", a1, a2);
if(a1 > a2)
printf("1\n");
else
printf("0\n");
}
}
}

QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动,使用 Azurus 作为主题。