[CF1270H]Number of Components

这个题是个比较傻逼的数据结构题,但是我想了一天多,说明我太菜了。
首先一个显然的结论,每一个联通块都必须是原序列中一段连续的区间,可以用反证法证明这个结论。
而相邻两个是否在同一个联通块里面相当于前缀min是否小于后缀max。
所以问题变成了统计有多少个位置的前缀min小于后缀max。这个我想了好久,后来发现我傻逼了。直接线段树分治,问题变成了插入,然后求答案。可以在插入一个元素之后,之前所有位置不可能从符合条件变成不符合条件。所以我们可以再开两棵线段树,一棵用于二分出新插入的数的影响区间,一棵用于维护哪些位置符合条件。
可以利用标记永久化的思想节省空间。
时间复杂度$O(q\lg n\lg q)

Tagged with:

发表评论