题解 P3613 【睡觉困难综合征】

2017-02-26 23:10:55


首先发现每一位不会互相影响,可以把每一位分开考虑,然后用树链剖分或者LCT维护这个树

修改直接修改,询问的时候算出来每一位填0,1经过这条链的变换之后得到的值

考虑贪心,从高往低,如果这一位填0可以得到1,那么填0一定是最优的

否则如果可以填1,就把这一位填为1

复杂度是nklog^2n或者nklogn,只能通过50%的数据

发现可以并行计算这k位,复杂度降为nlog^2n的树链剖分或者nlogn的LCT,可以通过100%的数据

这个题没有卡常,合并信息不是O( 1 )的算法没有通过是很正常的吧。。。

还有树链剖分没法做到logn,每条链建线段树也是log^2n的,还不能搞子树,似乎常数也一般。。。

最优复杂度是log^2n,不过期望下大概是lognloglogn的感觉

这个题的最优复杂度为O( n + q( logn + k ) ),至少目前来说是这样的