自动搬运

查看原文

来自洛谷，原作者为

	noip 对你说再见

搬运于2025-08-24 22:09:54，当前版本为作者最后更新于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 ) )，至少目前来说是这样的