[洛谷P4899][IOI2018] werewolf 狼人

这个题感觉比较神奇,其实并不是很难,但是我想了好久,说明我太菜了。
首先肯定想到建kruskal重构树,对狼形态和人形态都建一棵,然后问题变成了求两棵树各一棵子树中的点有没有交集。这个问题就是把子树转到dfs序上来做,相当于在一个二维平面内求一个矩形中有没有点。这个问题直接离线用树状数组做即可。

Tagged with:

发表评论