题解：P14638 [NOIP2025] 序列询问 / query

希望大家永远忘了我。

看见特殊性质 $D,E$ 非常嘟嘟。这样的特殊性质只会带来一个特性：被统计进答案的区间必然包含二等分（$D$）或四等分（$E$）点。

对跨过二等分点和四等分点的区间计数，是互不冲突的。这启示我们使用分治。

对于一个分治区间，考虑跨过中点 $mid$ 的贡献。按照分治套路，我们用右区间来更新左区间。令左端点为 $i$，右端点 $> mid$ 的最大的长度在 $[L,R]$ 内的区间的和为 $f_i$，则对题目中 $k_i$ 的贡献为 $k_i\gets\max(k_i,\max_{j=i}^{mid}f_j)$。维护这个 $f_i$ 的方式也很简单，考虑维护一个头小尾大的单调队列，队列元素是 $(mid,r]$ 区间的前缀和，每次将尾部长度和左区间后缀长度之和大于 $R$ 的区间 pop 掉即可。注意要同时满足长度至少为 $L$ 的限制。左区间贡献右区间同理。

每个分治层 $k_i\gets\max(k_i,\max_{j=i}^{mid}f_j)$ 更新即可，容易证得时间复杂度 $\mathcal{O}(nq\log n)$。

遗憾的是，好像过不了。

考虑分治在做什么。发现若有一个 $L$ 的长度下限，那么长度 $<L$ 的分支区间显然没用。否则将该分治区间的中点拍在 $[1,n]$ 的序列上。观察到，所有分治中点大概形成了一个 $2^k$ 等分的序列。

实际上，我们去钦定了区间必须经过中点，可以看作在 $[1,n]$ 上的关键点，一个区间合法必须跨过关键点。考虑若我们将所有 $2^k$ 等分点作为关键点，则对于 $\forall len\in [2^k,2^{k+1})$，这样的区间都满足经过恰好一个关键点。这样我们可以将分治区间的做法直接照搬到这个序列上。进一步的，对查询 $[L,R]$ 满足 $2^k\le L\le R\le 2^{k+1}$，我们容易扫描 $2^k$ 等分点序列实现 $\mathcal{O}(n)$ 单次求解。

考虑把上述结论扩展。预处理所有 $2^k$ 等分序列对单点 $i$ 的贡献 $g_{k,i}$。这样的序列显然只有 $\log_n$ 个。然后对每个单点位置 $i$ 实现 $\mathcal{O}(1)$ 查询 $\max_{k=l}^{r} g_{k,i}$。

每次查询形如若干个整块 $\forall k\in(bel_L,bel_R),[2^k,2^{k+1})$ 和散块 $[L,2^{bel_L}],[2^{bel_R},R]$。其中 $bel_i$ 表示 $i$ 所在的 $2^k$ 等分序列编号。

前文提到散块可以做到 $\mathcal{O}(n)$ 单次查询，加上每个位置做一个 $\mathcal{O}(1)$ 区间 $\max$，单次查询复杂度 $\mathcal{O}(n)$，所以总查询复杂度 $\mathcal{O}(nq)$，加上预处理，总复杂度 $\mathcal{O}(n\log^2 n+nq)$。