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

首先发现每一位不会互相影响，可以把每一位分开考虑，然后用树链剖分或者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 ) )，至少目前来说是这样的