【CF1017G】The Tree

Source and Judge

CF1017G
CF1017G

Record

3h

Analysis

请先思考后再展开

巧妙地转化题意:
初始所有点都是-1,表示消耗,每次操作单点+1
定义f表示向上的链上,最大后缀和(可跨过-1,不能为空)
则x是黑色当且仅当 $f(x) \geq 0$

那么这个操作二要怎么处理呢?
强行让所有人f都变成-1即可,这个可以全部恢复-1,然后对x修改,强行变成即使有后缀和也是-1即可
【hint:这里访问父亲的时候要特判根的情况……拍了超久】

考虑用线段树,以dfs序为下标,维护每个区间的data
如果我们能设计一个merg(left,right),注意是有序的,left和right在使用意义上是连续的(链或者dfs序区间)
那么询问就很好回答了,按照常规的树剖跳上去,按顺序merg好即可

唯一的问题就是merg如何实现
data存储区间的和、左端点的位置,以及最大后缀和(这样左边就可以计算了)
那么唯一需要考虑的,就是最大后缀和的左端点在left,显然一定是【左边的后缀和+右边的和】与原本比较

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans;
}
void qwrite(int num)
{
if(num>=10) qwrite(num/10);
putchar('0'+num%10);
}
void qwriteln(int num) {qwrite(num);puts("");}
const int MAX_N=110000;
struct Nod{int hou,dfn,tp,fa;}p[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,p[x].hou};p[x].hou=ln;}
int son[MAX_N],siz[MAX_N];
void pre(int x,int fa)
{
siz[x]=1;p[x].fa=fa;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
pre(y,x);siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
int id=0;
void getid(int x,int tp)
{
p[x].dfn=++id;p[x].tp=tp;
if(son[x]>0) getid(son[x],tp);
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].dfn==0 and y!=son[x]) getid(y,y);
}
}
struct Data{int sum,rmx;};
Data merg(Data left,Data right)
{
return (Data){left.sum+right.sum,max(left.rmx+right.sum,right.rmx)};
}
struct SegmentTree
{
struct Nod
{
int l,r;
Data s;
bool cl;
}p[MAX_N*4];
#define lc 2*x
#define rc 2*x+1
void clear(int x)//num->-1 rmx->-1
{
p[x].s=(Data){-(p[x].r-p[x].l+1),-1};
}
void build(int x,int l,int r)
{
p[x].l=l;p[x].r=r;
p[x].cl=0;clear(x);
if(l<r)
{
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
}
void pushdown(int x)
{
clear(lc);clear(rc);
p[lc].cl=p[rc].cl=1;
p[x].cl=0;
}
void change(int x,int pos,int c)
{
if(p[x].l==p[x].r)
{
p[x].s=(Data){c,c};
return;
}
if(p[x].cl) pushdown(x);
int mid=(p[x].l+p[x].r)>>1;
if(pos<=mid) change(lc,pos,c);
else change(rc,pos,c);
p[x].s=merg(p[lc].s,p[rc].s);
}
void white(int x,int fl,int fr)
{
if(p[x].l==fl and p[x].r==fr)
{
clear(x);p[x].cl=1;
return;
}
if(p[x].cl) pushdown(x);
int mid=(p[x].l+p[x].r)>>1;
if(fr<=mid) white(lc,fl,fr);
else if(fl>mid) white(rc,fl,fr);
else white(lc,fl,mid),white(rc,mid+1,fr);
p[x].s=merg(p[lc].s,p[rc].s);
}
Data ask(int x,int fl,int fr)
{
if(p[x].l==fl and p[x].r==fr) return p[x].s;
if(p[x].cl) pushdown(x);
int mid=(p[x].l+p[x].r)>>1;
if(fr<=mid) return ask(lc,fl,fr);
else if(fl>mid) return ask(rc,fl,fr);
else return merg(ask(lc,fl,mid),ask(rc,mid+1,fr));
}
}sgt;
int getf(int x)
{
Data now;bool bk=0;
while(x!=0)
{
int tp=p[x].tp;
if(bk==0) now=sgt.ask(1,p[tp].dfn,p[x].dfn),bk=1;
else now=merg(sgt.ask(1,p[tp].dfn,p[x].dfn),now);
x=p[tp].fa;
}
return now.rmx;
}
void main()
{
int n,q;scanf("%d%d",&n,&q);
for(int i=2;i<=n;i++) {int fa=qread();ins(fa,i);ins(i,fa);}
sgt.build(1,1,n);
pre(1,0);getid(1,1);
while(q--)
{
int op,x;scanf("%d%d",&op,&x);
if(op==1)
{
Data now=sgt.ask(1,p[x].dfn,p[x].dfn);
sgt.change(1,p[x].dfn,now.rmx+1);
}
else if(op==2)
{
sgt.white(1,p[x].dfn,p[x].dfn+siz[x]-1);
if(x!=1)//debug 拍了超久
{
int now=getf(p[x].fa);
sgt.change(1,p[x].dfn,min(-1,-now-1));
}
}
else
{
int col=getf(x);
if(col>=0) puts("black");
else puts("white");
}
}
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/cbab.html
转载请注明出处,谢谢!