Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

02/9
14:14
分块

BZOJ 3720 Gty的妹子树 树分块

Description

我曾在弦歌之中听过你, 檀板声碎,半出折子戏。 舞榭歌台被风吹去, 岁月深处尚有余音一缕…… Gty神(xian)犇(chong)从来不缺妹子…… 他来到了一棵妹子树下,发现每个妹子有一个美丽度…… 由于Gty很哲♂学,他只对美丽度大于某个值的妹子感兴趣。 他想知道某个子树中美丽度大于k的妹子个数。 某个妹子的美丽度可能发生变化…… 树上可能会出现一只新的妹子…… 维护一棵初始有n个节点的有根树(根节点为1),树上节点编号为1-n,每个点有一个权值wi。 支持以下操作: 0 u x 询问以u为根的子树中,严格大于x的值的个数。(u^=lastans,x^=lastans) 1 u x 把u节点的权值改成x。(u^=lastans,x^=lastans) 2 u x 添加一个编号为"当前树中节点数+1"的节点,其父节点为u,其权值为x。(u^=lastans,x^=lastans) 最开始时lastans=0。

Input

输入第一行包括一个正整数n(1<=n<=30000),代表树上的初始节点数。 接下来n-1行,每行2个整数u,v,为树上的一条无向边。 任何时刻,树上的任何权值大于等于0,且两两不同。 接下来1行,包括n个整数wi,表示初始时每个节点的权值。 接下来1行,包括1个整数m(1<=m<=30000),表示操作总数。 接下来m行,每行包括三个整数 op,u,v: op,u,v的含义见题目描述。 保证题目涉及的所有数在int内。

Output

对每个op=0,输出一行,包括一个整数,意义见题目描述。

Sample Input

2
1 2
10 20
1
0 1 5

Sample Output

2

HINT

 

Source

By Autumn

Solution

按照size分块,看父节点所在的块的大小是否超过√n, 没有就加入,否则新建一块。块与块之间也是树形结构,同样用邻接表存起来。

对于每个询问,块内二分,块外暴力。

然而我太菜了,写错了好几次……好在最终还是过了 o( ̄▽ ̄)ブ

PS:听说这题有更优的分块大小,可以自己去看~

 

02/8
11:00
分块

BZOJ 1086 王室联邦 树分块

Description

“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省,每个省都由他们王室联邦的一个成 员来管理。他的国家有n个城市,编号为1..n。一些城市之间有道路相连,任意两个不同的城市之间有且仅有一条 直接或间接的道路。为了防止管理太过分散,每个省至少要有B个城市,为了能有效的管理,每个省最多只有3B个 城市。每个省必须有一个省会,这个省会可以位于省内,也可以在该省外。但是该省的任意一个城市到达省会所经 过的道路上的城市(除了最后一个城市,即该省省会)都必须属于该省。一个城市可以作为多个省的省会。聪明的 你快帮帮这个国王吧!

Input

第一行包含两个数N,B(1<=N<=1000, 1 <= B <= N)。接下来N-1行,每行描述一条边,包含两个数,即这 条边连接的两个城市的编号。

Output

如果无法满足国王的要求,输出0。否则输出数K,表示你给出的划分方案中省的个数,编号为1..K。第二行输 出N个数,第I个数表示编号为I的城市属于的省的编号,第三行输出K个数,表示这K个省的省会的城市编号,如果 有多种方案,你可以输出任意一种。

Sample Input

8 2

1 2

2 3

1 8

8 7

8 6

4 6

6 5

Sample Output

3

2 1 1 3 3 3 3 2

2 1 8

HINT

 

Source

 

Solution

一道有意思的树分块的题目。

维护一个栈,在dfs的时候,先遍历一遍所有的儿子节点,再把当前点压入栈内,每次自下向上更新,如果≥B个城市,就放在同一个省里,由当前子树的根节点做省会。

可是这样就会有一个问题,如果一棵子树内的元素数不足B个,再去搜索下一棵子树的时候,合并的块可能不联通。

在dfs开始维护一个栈底,每次只能计算栈底以上的元素个数,每次合并也是只能合并栈底以上的元素,这样就可以啦。o( ̄▽ ̄)ブ

对于最后剩下的块,合并到最后一个块内即可。

 

Orz PoPoQQQ