【省选模拟】世界树(点分治)(单调队列)(启发式合并)

考场大力二分答案,把 ≥mid\ge mid≥mid 的设成 1,把 <mid<mid<mid 的设成 −1-1−1,若存在一条权值 ≥1\ge 1≥1 的长度 ∈[L,R]\in [L,R]∈[L,R] 的路径那么本次合法。 这个东西点分没有办法容斥,只有考虑一个子树拼接前面的其它子树。 这个东西是个单点修改区间加,所以考场我就码了个深度为下标的线段树,单修区查 maxmaxmax。 于是复杂度是美妙的 nlog(n)3nlog(n)^3nlog(n)3。 考虑把 [L,R][L,R][L,R] 的限制用单调队列来解决,这样就可以做到 nlog(n)2nlog(n)^2n