Codeforces Round 930 (Div. 1)
https://codeforces.com/contest/1936
D. Bitwise Paradox
对于给定$v$
长度$n$,正整数数组$a,b$
对于$[l,r]$若 $b_l | b_{l+1} | \cdots | b_r \ge v$, 则称区间$[l,r]$是好的，其中运算符是 bitwise or运算
区间美丽值$beauty([l,r])=\max(a_l,a_{l+1},\cdots,a_r)$ 且区间是 好的，否则为$\infty$
q个询问,两种操作
- 单点修改b, $b_i=x$
- 询问$[l,r]$的所有子区间中 最小的美丽值（好的子区间中最小的美丽值）
n,q 2e5
$a_i,b_i,v \in [1,10^9]$
5s
1024mb
我的思路
首先b是控制是否good, 而a是控制beauty的最大值的
先是想如果没有操作就是询问
那么注意到 最这[l,r] 增大 bitwise or 非严格单调递增，同时beauty也非严格单调递增
所以想for l=1..n, 对于每个 l 找最小的r使得它是good 的，
那么 对于[ql,qr],如果ql <= l, 那么以l为子区间左端点的贡献就是 最小的r，包裹起来的 a的max
因为 如果 qr < r，说明以$l$为起点的 任何区间都非good,无贡献，
如果qr>=r,说明l作为子区间左端点时，有且只有r..qr作为子区间右端点的贡献，而r是一定非严格最小的，所以r+1..qr不会有额外贡献
所以 可以预先处理成 [i]=>[r,max]
计算r就是 直接 做bit拆分的 每个bit求和 做比较， n logV复杂度，r随着i增加非严格单调递增，max是丢个优先队列，能同步完成的
那么查询就是 [ql,qr] 中 所有 min(max) |{r <= qr,max}
这可能要离线莫队
然后如果把上面n个 [l,r,max] 看成n次操作的话
那么实际上是二维平面里 [<=l, >=r]的地方 做了val=min(val,max)的运算
也可以 2d seg tree
然后问题来了，现在虽然不改动a,但是要改动$b_i=x$
而一个bi 将 影响那些 l <= i <=r的
这样 修改的 [l,r,max] 就是多个了
没想到怎么维护
题解
用线段树管理 b
对于值的每个bit位的1, 在线段树[l,r)区间记录首次和最后一次出现的位置
对于查询或修改 [ql <= l, r <= qr] 如果
- 需要对应bit是1
- 且是跨
[l,mid)[mid,r)中线的
那么 要么是[l,mid) 最右侧的1,要么是[mid,r) 最左侧的1
因为
- 如果包含更多，那么这一bit位不会有更多贡献
- 如果包含更少，那么和不包含是一样的效果
又max（a)的性质
如果 [l,p,mid) [mid,q,r),其中p,q分别是最右1和最左1的位置
如果max(a[p..mid)) <= max(a[mid,q]), 那么贪心选p, 因为 如果选的是q,那么选[p..q] 不会让结果更大，所以选q总能选p,选p不一定能选q
因此从高到低位 枚举首个大于v的bit位（v的当前位是0），那么更高位v是1的一定是1, 更高位是0的可以随意，更低位随意，
总结
D: 比赛时 abc花时间太多了，没时间想估计也想不出来？
哦 很有道理，要 bitwise or的 大于一个值，就是高位1都是1, 某个低位0是1即可，更低位任意，这样 对于 区间的answer 合并的关键就在“跨越分界线处”
所以 如果能解决 跨分界线的 >=问题 就能解决，这里 对应bitwise or 正好拆分 bit，然后大于等于变成 大于 只需要 目标值减1
感觉上只能感觉到像数据结构，和bit比较，但细节没想到
E: TODO
F: TODO