题解：P6749 『MdOI R3』Yoshino

首先因为等差数列公差为

1

，所以内部没用贡献，非

[l, r]

区间分为两部分：

L = [1, l-1]

和

R = [r+1, n]

，贡献分四类计算：

贡献类型	范围	计算	含义
类型 1	左部元素 $x$ 值域 $(R, V]$ （ $x > R$ ）	$cnt1 * len$	左部每个 $x$ 都比 $X$ 中所有元素大，共 $cnt1$ 个 $x$ ，每个贡献 $len$ 个逆序对
类型 2	右部元素 $x$ 值域 $[1, L)$ （ $x < L$ ）	$cnt2 * len$	右部每个 $x$ 都比 $X$ 中所有元素小，共 $cnt2$ 个 $x$ ，每个贡献 $len$ 个逆序对
类型 3	左部元素 $x$ 值域 $[L, R]$ （ $L ≤ x ≤ R$ ）	$x - L$	$X$ 中比 $x$ 小的元素有 $x - L$ 个（ $X$ 是 $L, L+1, ..., R$ ），每个 $x$ 贡献 $x - L$ 个
类型 4	右部元素 $x$ 值域 $[L, R]$ （ $L ≤ x ≤ R$ ）	$R - x$	$X$ 中比 $x$ 大的元素有 $R - x$ 个，每个 $x$ 贡献 $R - x$ 个

总贡献：

\Delta = (\text{cnt1} + \text{cnt2}) \times \text{len} + (\text{sum3} - \text{cnt3} \times L) + (\text{cnt4} \times R - \text{sum4})

其中：

$cnt1$ ：左部 $[1, l-1]$ 中值域 $(R, V]$ 的元素个数；
$cnt2$ ：右部 $[r+1, n]$ 中值域 $[1, L)$ 的元素个数；
$cnt3$ ：左部 $[1, l-1]$ 中值域 $[L, R]$ 的元素个数， $sum3$ 为这些元素的和；
$cnt4$ ：右部 $[r+1, n]$ 中值域 $[L, R]$ 的元素个数， $sum4$ 为这些元素的和。

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

cnt

和

sum

查询。

珂朵莉树（ODT）：维护序列的区间划分，每个节点存储 $(l, r, v)$ （位置范围 $[l, r]$ ，首项 $v$ ），支持 $split$ （分裂区间）和 $assign$ （合并区间）操作，复杂度均摊 $O(n+m)$ 。
分块：将原序列分为 $\sqrt n$ $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

左侧），贡献为：

\text{contribution}(A, B) = \sum_{x=s}^t \sum_{y=u}^v [x > y]

固定

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

。

因此总贡献可拆分为：

\text{contribution}(A, B) = \sum_{\substack{x = \max(s, u+1) \\ x \leq \min(t, v+1)}} (x - u) + \sum_{\substack{x = \max(s, v+2) \\ x \leq t}} (v - u + 1)

一次修改生成区间

[sv, tv]

，其对任意值

i

的贡献

f(i)

是分段函数：

0 & \text{if } i \leq sv, \\ i - sv & \text{if } sv < i \leq tv + 1, \\ tv - sv + 1 & \text{if } i > tv + 1. \end{cases}$$ 为了 $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}$。 发现是一个三维前缀和，通过展开前缀和式子得： $$\sum_{i=1}^n\sum_{j=1}^{i}\sum_{k=1}^ja_k=\frac{1}{2}[(n+1)(n+2)\sum_{i=1}^na_i-(2n+3)\sum_{i=1}^nia_i+\sum_{i+1}^ni^2a_i]$$。 然后就是一个树状数组维护多维前缀和的经典套路，开三个树状数组，分别维护 $x$，$i\times x$，$i^2\times x$。 cdq 分治时间复杂度 $O(n\log^2 n)$，颜色段均摊时间复杂度 $O(n+m)$。 总时间复杂度 $O(n\log^2 n)$。

题解：P6749 『MdOI R3』Yoshino

文章操作

相关推荐

评论

题解：P6749 『MdOI R3』Yoshino