题解：P6749 『MdOI R3』Yoshino

leather_handbag · 2025-11-13 16:21:16 · 题解

首先因为等差数列公差为 1，所以内部没用贡献，非 [l, r] 区间分为两部分：L = [1, l-1] 和 R = [r+1, n]，贡献分四类计算：

总贡献：

其中：

用 ODT 维护区间，用「分块+树状数组」维护「区间-值域」的个数和和，快速计算贡献公式中的 cnt 和 sum 查询。

• 珂朵莉树（ODT）：维护序列的区间划分，每个节点存储 (l, r, v)（位置范围 [l, r]，首项 v），支持 split（分裂区间）和 assign（合并区间）操作，复杂度均摊 O(n+m)。
• 分块：将原序列分为 \sqrt n 个块，每个块维护：
  • 两个树状数组：T1（统计块内元素的「和」，按值域存储）、T2（统计块内元素的「个数」，按值域存储）；
  • 标记 tag：若块被整体赋值为等差数列，tag 存储该等差数列的首项。

查询的时候查询 [l, r] 中值域在 [L, R] 内的元素个数和和：

• 散块：下推标记后暴力遍历元素，统计结果；
• 整块：若有标记，用等差数列求和公式直接计算：
  • 个数：\max(0, \min(R, tag+len-1) - \max(L, tag) + 1)；
  • 和：(\min(R,tag+len-1) + \max(L, tag))\times \frac{cnt}{2}；
• 无标记：直接查询树状数组 T1.ask(L, R) 和 T2.ask(L, R)。

时间复杂度 O(n\sqrt n\log n)。

虽然能过原题，但是这个复杂度还是太慢了，考虑修改的时间戳和逆序对形成三维偏序，考虑用树套树或 cdq 分治维护，因为覆盖是区间的所以考虑颜色段均摊。

把每个覆盖块看成一个点，考虑均摊的时候如何以低时间复杂度维护单次查询和更新。

考虑查询，对于每一个等差数列块 [l,r]，我们要算每个 i\in[l,r] 块右边有多少值 \le a_i。

我们设 c_i 表示 i 的个数，设 s_i 表示小于 i 的个数，设 f_i 表示 \sum_{j=1}^is_i 也就是小于等于 i 的 s_i 的和，那么对于每个块答案就是 f_r-f_{l-1}，但是时间复杂度爆了，因为块的数量不是均摊的。

考虑查询是全局的，于是尝试反过来算修改对全局逆序对的贡献， 首先因为等差数列公差为 1，所以内部没用贡献， 对于区间 A[s,t] 和 B[u,v]（A 在 B 左侧），贡献为：

固定 x，内层求和 \sum_{y=u}^v [x > y] 的结果是 y < x 的数量，分三类：

若 x\le u：0；

若 u < x \le v+1：x - u；

若 x > v+1：v - u + 1。

因此总贡献可拆分为：

一次修改生成区间 [sv, tv]，其对任意值 i 的贡献 f(i) 是分段函数：

为了 O(1) 表示 f(i)，利用差分标记其变化率：

在 i=sv+1 处标记 +1；在 i = tv + 2 处标记 -1。

对标记做两次前缀和即可还原 f(i)：

查询时需计算值范围 [L,R] 的总贡献，即\sum_{i=L}^R f_i。

设 g_i 表示 \sum_{j=1}^i f_j，答案就是 g_r-g_{l-1}。

发现是一个三维前缀和，通过展开前缀和式子得：