既见君子

同济医学生的起落落落落人生记录

hdu 5574 Colorful Tree 题解

题目大意:

给定一颗每个点都有颜色的树,有两个操作

1.将一个子树全部染成颜色c

2.查询一个子树内的颜色个数


题解:

1.首先每一个1操作打在子树的根节点上,然后把这颗子树内部的所有标记全部干掉。

2.树链剖分维护每个点的答案。

3.对一个删除标记的处理:

  找到它相同颜色的关于这颗子树的前驱和后继,求一下lca,取更深的那个,把[x,lca)这条链的所有答案-1.

4.对一个加入标记的处理:

    同上,-1->+1,然后子树赋值为1

5.对于怎么拿到一个子树内部的所有标记,就开一个全局set,按照dfs序作为比较函数,每次就在set里面lower_bound两个端点即可.

6.对于怎么找到这个点的前驱和后继,就开颜色个数那么多个set,也每次lower_bound就好啦.

7.这两个set在做标记处理的时候进行加入和删除即可.


other:

1.某邱老师来讲课的时候讲过,于是那个时候被yjq秒了之后就没有细细讲,于是今天酱神出这道题来练习的时候大家都一脸懵逼,在我告诉他们有老师讲过的时候,变成了彻底懵逼.

2.然而那个时候我都不知道自己懂没懂了(也许问了很久之后问懂了也也许没有),反正今天不会,为了加深记忆还是来写一发题解.

3.看来我以前的知识还是有好多讲过的并没理解并没掌握,以后还是要好好做笔记,今天到底写不写这道题呢...ovo.

//yjq表示:"我都想好了邱老师来讲课的时候我就把题全部秒了然后你们什么都听不到"...臭不要脸.

评论(5)
热度(2)
©既见君子
Powered by LOFTER