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

yyyx_ · 2025-11-30 12:00:17 · 题解

希望大家永远忘了我。

看见特殊性质 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)。