题解

kczno1 2018-03-20 9:32:08 2018-03-20 9:32:39

分块

每个块维护块内每个长度下or的最大值

修改时
块内暴力重新计算每个长度下or的最大值
就是枚举右端点
然后到他的or和不同的左端点只有log种 枚举就可以了
时间O(n/k*log) (设分成k块)

询问时
答案在块内的情况:
check每个块
如果可以把答案减少1,就更新答案,然后重复操作
否则退出。
时间O(k+n/k)

如果答案跨过块:
从左到右枚举块

同时维护块左边所有不同的后缀or和
具体就是从一个块到下一个块的时候
把所有不同的后缀or和都or上自己整个块的or和
然后再加入自己所有不同的后缀or和(提前维护好)
之后去一下重
时间O(k*log)

现在考虑答案右端点在块内,左端点在块左边的情况
然后从左到右枚举块内所有不同前缀or和(提前维护好)
如果他跟 当前最大的在块前面的后缀or和 的or和>=k
就更新答案并删除当前最大的在块前面的后缀or和 然后重复操作
否则退出。
时间O(k*log)

k取sqrt(n)
总时间O(n*sqrt(n)*log(n))

共 6 条回复

Master_Yi

qym2008

讲得好啊!

xiaohuang

TeX parse error: Missing argument for \text

xiaohuang

1

xiaohuang

哈哈哈

LittleRed

1s有点卡常数啊……