【奇思妙想】关于线段树与异或

ningago @ 2022-03-30 15:47:33

by rxjdasiwzl @ 2022-03-30 15:51:09

先问能不能，再问怎么做。答案是不能。

by rxjdasiwzl @ 2022-03-30 15:51:20

https://www.luogu.com.cn/problem/P5670

by donghanwen1225 @ 2022-03-30 15:52:59

楼上正解，但是这东西应该只有伪多项式算法。也就是说复杂度要依赖于值域。

by StarLbright40 @ 2022-03-30 15:54:59

拆成 log值域 个存 01 序列的线段树（确信

然后就是 O(nlognloga)（

by ღꦿ࿐ @ 2022-03-30 15:55:57

@星光0000 不行啊，没法区间加，要进位

by 2018ty43 @ 2022-03-30 15:59:47

分块可以，考虑 P8257 [CTS2022] 普罗霍洛夫卡

by BlankAo @ 2022-03-30 16:05:17

@2018ty43 大佬可以教我怎么做吗orz

by 2018ty43 @ 2022-03-30 16:13:29

@BlankAo 我也不会，看lxl题解

by BlankAo @ 2022-03-30 16:16:43

@2018ty43 额给个链接可以吗thx

by 2018ty43 @ 2022-03-30 16:17:56

不过好像有个 保证每一时刻序列单 调递增，且相邻位置相差0或1 的限制