【BZOJ 4538】[HNOI2016] 网络

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4538
神犇题解：http://krydom.com/bzoj4538/

解题报告

这题我先说一种怪怪的做法 QwQ
考虑使用主席树，第一维是权值（用BIT搞成后缀和），第二维是DFS序
这样的话，对于询问我们可以在第一维的权值上进行二分
对于每一次二分 $ a$ ，我们可以通过判断覆盖该点的区间个数是否等于所有不小于 $ a$ 的区间个数是否相等

这样话，原问题转化为：在主席树上的区间加减问题
这一块的时空复杂度是 $ O(n{\log ^3}n)$ 的
然后考虑上二分的 $ log$ 这样的话，复杂度就是 $ O(n{\log ^4}n)$ 的
这种做法是自己YY的，感觉很有道理的样子
然而懒得写代码了，也不知道对不对

另外的话，再说一说正解吧！
考虑一条路径，说白了就是查询路径上的点的时候不查到该路径
查询非该路径上的点的时候查询到该路径
这时考虑树链剖分的话，该路径对应的 $ {log(n)}$ 个区间应该忽略，其他部分添加上这个路径的信息
因为是一整块区间抠掉 $ {log(n)}$ 个区间，所以剩余部分也只会有 $ {log(n)}$ 个区间
于是树链剖分暴力搞一搞就可以辣！
时空复杂度比之前的做法应该要稍微优越一点