Luogu5065 [Ynoi2014] 不归之人与望眼欲穿的人们

题意：维护长为 的序列 。支持：

• 单点修改。

• 询问满足区间 or 和大于等于一个数的区间的最短可能长度，或指出无解。

，，时限 。

---

相关题目 ： Luogu3794 签到题IV

分块 ：

记块长为 。

先考虑如何求解静态全局询问。

对于一个右端点，左端点对应的本质不同 or 值只有 个，于是容易双指针 计算。

对于每个块，记录每个长度的最大 or 和，前后缀本质不同 or 和。

查询时，对两边的散块内部可以单独跑一次，将其合成整块。

考虑答案区间在块内的情况，大力枚举每个块，若当前答案能减小则不断减小，复杂度为 。

考虑答案区间跨过两块的情况，枚举右端点所在的块，维护该块之前左端点的本质不同 or 和。

每经过一个块，将之前的左端点 or 上这个块，再加入这个块内部的后缀，然后去重。

在每个分界线处，双指针求出答案。复杂度为 。

令 即可做到 。

线段树：

用线段树维护序列 ，对于每个线段树节点，维护本质不同的前缀 or 和与后缀 or 和。

每次修改后，在每个受到影响的节点处暴力计算跨越分界线 的区间的 or 和。这些区间有 个。

对于每个长度，用堆来维护最大值。将这些最大值再用线段树维护，查询时只需线段树上二分。

修改的复杂度为 ，查询的复杂度为 。

拼在一起？：

用线段树维护每个块，每个线段树节点维护区间内长为 的最大区间 or 和。

合并时，考虑两个儿子的贡献，以及跨越中点的 个区间的贡献。

若块大小为 ，这个复杂度是 。

我们令 即可做到 。

卡常：在区间长度较小时跑暴力，这样可以同时减小时空常数。