Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom7月前

12/7
16:05
树链剖分 线段树

[bzoj 2243] [SDOI2011]染色

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给定一棵有n个节点的无根树和m个操作,操作有2类:

1、将节点a到节点b路径上所有点都染成颜色c

2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含2个整数nm,分别表示节点数和操作数;

第二行包含n个正整数表示n个节点的初始颜色

下面 行每行包含两个整数xy,表示xy之间有一条无向边。

下面 行每行描述一个操作:

“C a b c”表示这是一个染色操作,把节点a到节点b路径上所有点(包括ab)都染成颜色c

“Q a b”表示这是一个询问操作,询问节点a到节点b(包括ab)路径上的颜色段数量。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每个询问操作,输出一行答案。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3
1
2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

数N<=10^5,操作数M<=10^5,所有的颜色C为整数且在[0, 10^9]之间。

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

树链剖分,注意颜色的合并

 

[bzoj 2243] [SDOI2011]染色