CF1208H Red Blue Tree

CF1208H Red Blue Tree

原本应该放在这里但是这题过于毒瘤。。单独开了篇blog

首先考虑如果$k$无限小,那么显然整个树都是蓝色的。随着$k$逐渐增大,每个点都会有且仅有一次变色,我们考虑维护这个变色的时间$t$。如果每个点的变色时间都已经被算出来,那么我们可以轻易解决题目的查询操作和修改$k$, 也就是说修改$k$本身就是个假操作。。只需要考虑的是修改单点颜色。

修改单点颜色,看起来就很$ddp$。树链剖分后,用$f(x) = \{a,b\}$表示点$x$重儿子是 R 时的临界值是$a$,重儿子是 B 时临界值是$b$。

发现$f$这个东西是可以合并的!于是可以愉快地用线段树维护了呢~

但是除开重儿子怎么做呢,考虑每个点再开一个 BST 维护轻儿子当前的边界值。这个可以预处理的时候实现。同时我们意识到$\sum x$($x$是边界值 ) 是$n$级别的,所以我们可以对于每个点暴力出最开始的边界。具体的暴力方法是在build链剖后的线段树时先处理右子树,这样总可以保证处理到一个点时它的轻儿子都已经被插入到了它自己的平衡树,然后直接枚举边界值在平衡树判断就好了。

由于每次修改一个叶子,它的祖先的边界变化量是$O(1)$的,所以修改的复杂度是$O(log^2n)$

只是很难写

Orz LJZ_C 吊踩标算

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200006
int n , k;

#define Update( cur ) if( cur -> left -> size ) cur -> size = cur -> left -> size + cur -> right -> size , cur -> value = cur -> right -> value
#define new_Node( s , v , a , b ) ( & ( * st[ cnt++ ] = Node( s , v , a , b ) ) )
#define Merge( a , b ) new_Node( a -> size + b -> size , b -> value , a , b )
#define ratio 4
namespace BST {
int cnt , s , a;
struct Node {
int size , value;
Node * left , * right;
Node( int s , int v , Node * a , Node * b ) : size( s ) , value( v ) , left( a ) , right( b ) {}
Node() {}
} * root[1000000] , * father , * st[1000000] , t[1000000] , * null;

inline void maintain( register Node * cur ) {
if( cur -> left -> size > cur -> right -> size * ratio ) cur -> right = Merge( cur -> left -> right , cur -> right ) , st[ --cnt ] = cur -> left , cur -> left = cur -> left -> left;
if( cur -> right -> size > cur -> left -> size * ratio ) cur -> left = Merge( cur -> left , cur -> right -> left ) , st[ --cnt ] = cur -> right , cur -> right = cur -> right -> right;
}

int find( int x , Node * cur ) {
if( cur -> size == 1 ) return cur -> value;
return x > cur -> left -> size ? find( x - cur -> left -> size , cur -> right ) : find( x , cur -> left );
}

int Rank( int x , Node * cur ) {
if( cur -> size == 1 ) return 1;
return x > cur -> left -> value ? Rank( x , cur -> right ) + cur -> left -> size : Rank( x , cur -> left );
}

void insert( int x , Node * cur ) {
if( cur -> size == 1 ) cur -> left = new_Node( 1 , min( cur -> value , x ) , null , null ) , cur -> right = new_Node( 1 , max( cur -> value , x ) , null , null );
else insert( x , x > cur -> left -> value ? cur -> right : cur -> left );
Update( cur );
maintain( cur );
}

void erase( int x , Node * cur ) {
if( cur -> size == 1 ) * father = cur == father -> left ? * father -> right : * father -> left;
else father = cur , erase( x , x > cur -> left -> value ? cur -> right : cur -> left );
Update( cur );
maintain( cur );
}

void init( ) {
null = new Node( 0 , 0 , 0 , 0 );
for( int i = 0 ; i < 1000000 ; ++ i ) st[i] = & t[i] , root[i] = new Node( 1 , 0x7f7f7f7f , null , null );
}

}

int head[MAXN] , nex[MAXN << 1] , to[MAXN << 1] , ecn = 0;
void ade( int u , int v ) {
nex[++ecn] = head[u] , to[ecn] = v , head[u] = ecn;
}
int fa[MAXN] , siz[MAXN] , hea[MAXN] , dep[MAXN] , top[MAXN] , tig[MAXN] , bac[MAXN] , en[MAXN] , clo;
void dfs( int u , int faa ) {
siz[u] = 1 , dep[u] = dep[faa] + 1;
for( int i = head[u] ; i ; i = nex[i] ) {
int v = to[i];
if( v == faa ) continue;
fa[v] = u;
dfs( v , u );
siz[u] += siz[v];
if( !hea[u] || siz[v] > siz[hea[u]] ) hea[u] = v;
}
}
void dfss( int u , int too ) {
tig[u] = ++ clo , bac[clo] = u , en[too] = u , top[u] = too;
if( !hea[u] ) return;
dfss( hea[u] , too );
for( int i = head[u] ; i ; i = nex[i] ) {
int v = to[i];
if( v == fa[u] || v == hea[u] ) continue;
dfss( v , v );
}
}

int col[MAXN];

struct node{
int l , r;
node( int L = 0 , int R = 0 ) : l(L) , r(R) { }
} T[MAXN << 2] , red( 0x3f3f3f3f , 0x3f3f3f3f ) , blu( -0x3f3f3f3f , -0x3f3f3f3f ) ;
int rec[MAXN];
// T[rt].l : if rt's heavy son is red , the value k to satisfy that this node is red
// T[rt].r : if rt's heavy son is blu , the value k to satisfy that this node is red
// b : 0 , r : 1
bool judge( int u , int k , int d ) {
// return we add d red nodes to its son if the node is red.
int B = BST :: Rank( k + 1 , BST :: root[u] ) - 1;
int R = BST :: Rank( 0x7f7f7f7f , BST :: root[u] ) - 1 - B;
return k >= R - B - d;
}
void update( int u , int& k , int d ) {
while( !judge( u , k , d ) ) ++ k;
while( judge( u , k - 1 , d ) ) -- k;
}
void work( int rt , int u ) {
if( col[u] == 0 ) {
T[rt] = red;
} else if( col[u] == 1 ) {
T[rt] = blu;
} else {
update( u , T[rt].l , 1 );
update( u , T[rt].r , -1 );
}
}
node merge( node a , node b ) {
node ret;
ret.l = min( max( b.l , a.l ) , a.r );
ret.r = min( max( b.r , a.l ) , a.r );
return ret;
}
void pushup( int rt ) {
T[rt] = merge( T[rt << 1] , T[rt << 1 | 1] );
}
node query( int rt , int l , int r , int L , int R ) {
if( l == L && r == R ) return T[rt];
int m = l + r >> 1;
if( R <= m ) return query( rt << 1 , l , m , L , R );
if( L > m ) return query( rt << 1 | 1 , m + 1 , r , L , R );
return merge( query( rt << 1 , l , m , L , m ) , query( rt << 1 | 1 , m + 1 , r , m + 1 , R ) );
}
void build( int rt , int l , int r ) {
if( l == r ) {
int u = bac[l];
work( rt , u );
if( u == top[u] && fa[u] )
BST :: insert( ( rec[u] = ( query( 1 , 1 , n , l , tig[en[u]] ) ).l ) , BST :: root[fa[u]] );
return;
}
int mid = l + r >> 1;
build( rt << 1 | 1 , mid + 1 , r ) , build( rt << 1 , l , mid );
pushup( rt );
}
void mdfy( int rt , int l , int r , int p ) {
if( l == r ) { work( rt , bac[l] ); return; }
int m = l + r >> 1;
if( p <= m ) mdfy( rt << 1 , l , m , p );
else mdfy( rt << 1 | 1 , m + 1 , r , p );
pushup( rt );
}
void modify( int x , int c ) {
col[x] = c;
while( x ) {
mdfy( 1 , 1 , n , tig[x] );
x = top[x];
if( fa[x] != 0 ) {
BST :: erase( rec[x] , BST :: root[fa[x]] );
BST :: insert( rec[x] = (query( 1 , 1 , n , tig[x] , tig[en[x]] ).l ) , BST :: root[fa[x]] );
}
x = fa[x];
}
}

int main() {
BST :: init( );
cin >> n >> k;
for( int i = 1 , u , v ; i < n ; ++ i ) {
scanf("%d%d",&u,&v);
ade( u , v ) , ade( v , u );
}
for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&col[i]);
dfs( 1 , 1 );
dfss( 1 , 1 );
build( 1 , 1 , n );
int q , opt , v , c; cin >> q;
while( q-- ) {
scanf("%d",&opt);
if( opt == 1 ) {
scanf("%d",&v);
printf("%d\n",( query( 1 , 1 , n , tig[v] , tig[en[top[v]]] ).l ) <= -k);
} else if( opt == 2 ) {
scanf("%d%d",&v,&c);
modify( v , c );
} else {
scanf("%d",&c);
k = c;
}

}
}
文章作者: yijan
文章链接: https://yijan.co/old56/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog