文档章节

CF1208H Red Blue Tree

o
 osc_964dc088
发布于 2019/09/22 00:23
字数 1444
阅读 39
收藏 0
red

「深度学习福利」大神带你进阶工程师,立即查看>>>

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 吊踩标算

#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;
		}
		
	}
}
o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Go-node

Go-node 是一个用 Go 语言实现的 Erlang/OTP node 已支持的功能: Publish listen port via EPMD Handle incoming connection from other node using Erlang Distribution Protocol Spawn E......

匿名
2013/01/25
1.5K
1
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.4K
1
PHP web 服务器--YACS

YACS 是一个强大的 PHP 脚本,可以让你维护一个动态的 Web 服务器。 特性: - Runs on your own server, or on a shared web site - Post articles with web forms, by e-mail, or remotely ......

匿名
2013/03/18
864
0
TkTreectrl

TkTreectrl (TkinterTreectrl) 模块封装了 treectrl Tk 扩展以便在 Python/Tkinter 中使用。 The treectrl widget allows you to create fancy things like sortable multi-column list boxe......

匿名
2012/11/21
538
0
XUI Lib

XUI 是一个高效、灵活易用的 Windows UI 库,使用 C++ 编写,基于 ATL 库。 Features: Layout by XML. Full basic controls: Static, Button, Edit, List (by aggregation), Tree, Animation......

匿名
2012/11/29
1.4W
0

没有更多内容

加载失败,请刷新页面

加载更多

一年Node.js开发开发经验总结

写在前面 不知不觉的,写Node.js已经一年了。不同于最开始的demo、本地工具等,这一年里,都是用Node.js写的线上业务。从一开始的Node.js同构直出,到最近的Node接入层,也算是对Node开发入门...

osc_2fb62vw0
12分钟前
0
0
详解斜率优化

详解斜率优化 斜率优化的话前几个月学过一次,然后感觉会了,结果今天遇到个题,比赛时花了1h硬敲没怼出来,然后又去看了看人家的讲解,加上自己疯狂yy,才发现(原来很水嘛)上次只是略懂皮...

osc_eumlh0pn
12分钟前
0
0
pytest文档46-关于https请求警告问题(InsecureRequestWarning: Unverified HTTPS request is being made)

前言 使用 pytest 执行 https 请求用例的时候,控制台会出现警告:InsecureRequestWarning: Unverified HTTPS request is being made. Adding certificate verification is strongly advised......

osc_8s3utzxr
14分钟前
8
0
进程间通信和线程间通信的几种方式

进程间通信和线程间通信的几种方式 进程、线程、协程之概念理解 进程和线程、协程的区别 进程 进程(Process)是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的...

osc_we9lokaj
15分钟前
0
0
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。在构造过程中,请注意区分大小写。比如"Aa"不能当做一个回文字符串。注 意:假设字符串的长度不会超过 1010。

给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。在构造过程中,请注意区分大小写。比如"Aa"不能当做一个回文字符串。注 意:假设字符串的长度不会超过 1010...

osc_kedi1mvz
15分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部