3log 做法：不归之人与望眼欲穿的人们
Tangninghaha
·
·
题解
wtc 讲的 n\log^{3} 做法。Orz
题目大意
给定一个长为 n 的数组 a，有 m 次操作，每次操作形如：
1 i x 表示将 a_i 修改为 x。2 k 表示查询最小的 l，使得存在一个长度为 l 的区间或和大于等于 k。无解输出 -1。
## 解法
首先有经典结论：对于一个固定的右端点，只有 $\log_2 a$ 个或和不同的区间。因为左端点越向左，或和每一个二进制位只会由 $0$ 变 $1$，最多变化 $\log a$ 次。
在一棵线段树上，每个节点维护这个节点表示的区间，前缀或和不同的区间，后缀或和不同的区间。
再维护一棵下标为长度，值为或和最大值的线段树，查询时只需要在线段树上二分即可。底层需要用 `set` 或其它什么东西维护一下，因为可能会有删除操作。
第一棵线段树合并儿子时，将左儿子的后缀和右儿子的前缀两两配对合并，加入到第二棵线段树上。注意这时要记得去重，笔者去重写错获得 $95$ 分，还以为常数太大了。修改时直接递归到底层修改，然后往上合并即可。注意只修改包含修改位置的区间。
分析一下复杂度，下面认为 $n$ 和 $m$ 同阶：建树时有 $O(n)$ 个节点，每一个节点合并出 $O(\log^2)$ 个区间，这些区间在第二棵线段树上修改，每一次修改是 $O(\log n)$ 的：$O(\log n)$ 时间找到对应叶子，$O(\log n)$ 时间插入到底层数据结构中。修改时，由于只对包含修改点的区间进行修改，包含这个点只有 $O(\log^2 n)$ 个区间，故修改复杂度也是正确的。查询是 $O(\log n)$ 的线段树二分。
实际写出来由于常数过大，会 T 掉一个点。可以将第二棵线段树换成一个分块套对顶堆，理论复杂度退化，但由于常数很小，可以通过。
块长越大，询问越快，修改越慢，最后一个点修改非常多，其它点询问多。故块长调大一些能够获得更少的总用时，在块长为 $128$ 时笔者的代码最快。
## 提交记录
[总用时 1.59s](https://www.luogu.com.cn/record/202915766)