[CCO 2024] Heavy Light Decomposition

前置知识

分块，DP

简要题意

定义“好的数组”为一个数组内交替出现“轻元素”和“重元素”，轻元素即其在这个数组内是唯一的，重元素即其在数组内出现多次。

有 $n$ 个正整数 $a_i$，求其有多少种划分方案能使划分后的子数组均为好的数组。

分析样例

我们首先要搞懂一个东西，就是划分后好的数组，是指这个子数组是好的，在这个子数组内的轻重元素与原数组并没有关系，每个子数组是互相独立的。

对于样例一，其划分方案如下：

- $[1], [2], [3], [2], [3]$

- $[1], [2, 3, 2], [3]$

- $[1], [2], [3, 2, 3]$

- $[1, 2, 3, 2], [3]$

对于样例二，其划分方案如下：

- $[1], [2], [1], [3], [1]$

- $[1, 2, 1], [3], [1]$

- $[1, 2, 1, 3], [1]$

- $[1], [2], [1, 3, 1]$

- $[1], [2, 1, 3, 1]$

- $[1, 2, 1, 3, 1]$

不明白的建议手推一下。

思路分析

考虑转移

我们定义 $dp[i]$ 为前 $i$ 个元素的合法划分的方案数。

那么，转移方程很显然：$dp[i] = \sum dp[j]$，其中 $j < i$ 且 子数组 $[j + 1, i]$ 是好数组。

实际上含义就是在 $j$ 处划分，新增一个子数组 $[j + 1, i]$，方案累加前 $j$ 个元素的方案数。

考虑好数组的约束

如果 $[j + 1, i]$ 为好的数组，那么需要满足：

1. 类型交替：即数组内的元素轻重交替。

2. 奇偶性约束：如果重元素第一次出现在奇数位，那么奇数位全是重元素，反之。

因此我们如果直接枚举所有的 $j$ 去验证 $[j + 1, i]$ 是否为好数组，时间复杂度为 $O(n ^ 2)$。

考虑优化

对于当前的位置 $i$，我们设其元素大小为 $v$，用 $odd[v]$ 和 $even[v]$ 来记录 $v$ 在奇数和偶数位最近的出现位置，这样的话可以确定 $j$ 的下界。

为了保证子数组 $[j + 1, i]$ 满足类型交替，需要避免 $v$ 元素在数组内出现奇偶性冲突，那么若 $j + 1 < \min(odd[v], even[v])$ 的话，则会使其冲突。

因此我们使 $minL$ 取所有元素 $min(odd[v], even[v]) + 1$ 的最大值，因此 $j > minL - 1$。

然后是最重要的分块，我们将原数组分块，每个块维护两个核心内容，$sum[k][b]$ 表示 $b$ 块满足在奇偶性 $k$ 下的合法的 $dp[j]$ 之和，$kpos[k][b]$ 是在 $k$ 的奇偶性下块 $b$ 是否满足。另外，为了维护分块时的单个元素， 我们维护 $pos[k][i]$ 是单个位置的 $i$ 是否满足奇偶性 $k$。

当我们查询 $[l, r]$ 内符合条件的 $dp[j]$ 之和时，对于整块，只需要判断 $kpos$ 是否有效，然后累加 $sum$ 即可，对于单个的块边缘的元素，则需要满足 $kpos$ 和 $pos$，有效则累加 $dp[j]$。

在区间更新时，只需要标记区间有效和无效，在完整的块上更新 $kpos$，零散的元素更新 $pos$ 和 $sum$。

时间复杂度

分块的单次查询和更新的时间复杂度为 $O(\sqrt{n})$，时间复杂度为 $O(n \sqrt n)$。

简单卡常即可，最慢的点才两秒出头，对于四秒的时间限制完全够用。

Subtask1: n,m≤100

注意到我们可以枚举每一对 (E,S) 并判断 Bob 是否必胜，最后将必胜的方案数除以 nm 就是答案。

判断是否必胜我们直接将边 E 删去并从起点 S 开始搜索即可，时间复杂度 O(n2m)。期望得分 30pts。

Subtask2: w=1

除非 S 是叶子且 E 恰好是 S 的唯一出边，Bob 都是必胜的。统计是简单的，不再赘述。

Subtask3: n,m≤5000

考虑从边双连通分量入手，我们枚举 E。

若 E 不是割边，那么删除 E 不会影响 S 所能到达的点/边集。只要原图中还存在边权与 E 相等的边，那 Bob 就是必胜的，贡献为 n。

若 E 是割边，那么删除 E 会将边双树分为两个连通块，而 S 只能遍历其所处的连通块，所以 Bob 必胜等价于该连通块中有边权与 E 相等的边。直接遍历两个连通块来判断即可。

割边的数量可以达到与 n 同阶，故时间复杂度为 O(nm)。期望得分 60pts。

Subtask3: n,m≤106

考虑优化 E 是割边时的判断过程。注意到一个连通块必定是边双树中的一颗子树或者全树扣掉一颗子树，而后者可以直接用全局减去该子树得到。于是问题等价于求一棵子树中边权与根的父边相等的边的数量。

这个问题的做法非常多，容易 O(n) 实现，期望得分 100pts。

首先来看这个什么三元组。

定义一种特殊的三元组：(x,y,z)，其中x,y,z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：

x,y,z 是整数,x<y<z,y−x=z−y；x,z 颜色相同。

满足上述条件的三元组的分数规定为 (x+z)×(number_x+number_z)。

诶，我们发现，这个「分数」跟 y 之间，半个咕值的关系都没有啊 QAQ？

于是，秒懂：

∵y−x=z−y

∴x+z=2y

又，2y 是偶数，所以 x,z 同奇偶。

这就是 y 的用处啦QAQ。

由于不同颜色的 x,z 肯定不会产生分数，所以我们可以先把这个「狭长的纸带」按照颜色分类，最后把每种颜色产生的分数加起来即可。

然后不同奇偶性的 x,z 也不会产生分数，所以把每个颜色种类按照奇偶性再分个类，最后把奇数产生的分数和偶数产生的分数加起来即可。

举个例子：

格子编号   1 2 3 4 5 6 7 8 9 10

格子上的数字 5 5 3 2 2 2 7 8 2 5

格子颜色   2 2 1 1 2 1 2 2 2 1

那么先按照颜色分类：

颜色为 1 的：

格子编号   3 4 6 10

格子上的数字 3 2 2 5

格子颜色   1 1 1 1

颜色为 2 的：

格子编号   1 2 5 7 8 9

格子上的数字 5 5 2 7 8 2

格子颜色   2 2 2 2 2 2

再按照编号分类：

颜色为 1 ，编号为奇数的：

格子编号   3

格子上的数字 3

格子颜色   1

颜色为 1 ，编号为偶数的：

格子编号   4 6 10

格子上的数字 2 2 5

格子颜色   1 1 1

颜色为 2 ，编号为奇数的：

格子编号   1 5 7 9

格子上的数字 5 2 7 2

格子颜色   2 2 2 2

颜色为 2 ，编号为偶数的：

格子编号   2 8

格子上的数字 5 8

格子颜色   2 2

好的，分类完毕！

那么，怎么计算分数呢？

当然可以 O(n2) 暴力算一通。做法显然，这里不多说了。

不过，复杂度铁定爆炸。

考虑更优的做法。

拿上面那个例子中，颜色为 2 ，编号为奇数的 4 个格子来举个例子：

由于颜色显然是一样的，而且计算分数也和颜色无关，所以就不用再管颜色了。

然后设 f[i] 为这一组中第 i 个数的编号，n[i] 为这一组中第 i 的数的颜色。

i  1 2 3 4

f[i]1 5 7 9

n[i]5 2 7 2

先看前两个数，他们产生的分数为：

(f[1]+f[2])×(n[1]+n[2])

然后考虑当第三个数加入时，多出来的分数。

第三个数和第一个数会产生一些分数：

(f[1]+f[3])×(n[1]+n[3])

第三个数和第二个数也会产生一些分数：

(f[2]+f[3])×(n[2]+n[3])

所以多出来的分数为：

(f[1]+f[3])×(n[1]+n[3])+(f[2]+f[3])×(n[2]+n[3])

展开后，得到：

f[1]⋅n[1]+f[1]⋅n[3]+f[3]⋅n[1]+f[3]⋅n[3]+f[2]⋅n[2]+f[2]⋅n[3]+f[3]⋅n[2]+f[3]⋅n[3]

把 n[3] 和 f[3] 提取出来：

f[1]⋅n[1]+f[1]⋅n[3]+f[3]⋅n[1]+f[3]⋅n[3]+f[2]⋅n[2]+f[2]⋅n[3]+f[3]⋅n[2]+f[3]⋅n[3]

（标红的是提取出来的 n[3]，标蓝的是提取出来的 f[3]）

n[3]⋅(f[1]+f[2]+f[3])+f[3]⋅(n[1]+n[2]+n[3])+n[1]⋅f[1]+n[2]⋅f[2]

从这个式子中，我们看出，只需要处理 f 数组，n 数组，还有 f[i]⋅n[i] 的前缀和即可。

后面也是一个一个添加进来，一样的。

该题解来自洛谷

题目大意：给出一个 $n$ 点 $m$ 边的 DAG，每个点有两个权值 $a_i$，$b_i$.保证 $a, b$ 均为 $1\sim n$ 的排列。有三种操作：交换 $a_{x}$, $a_{y}$、交换 $b_{x}$, $b_{y}$、找数。

找数：给定x, l, r，找出最大的$b_{y}$满足x能到达y，l≤$a_{y}$≤r

数据范围：1≤n, q≤1e5，1≤m≤2e5，数据组数不超过3

解法思路：

本题核心为bitset的运用。

由DAG的连通性可知，最优时间复杂度不超过O($\frac{nm}{\omega}$)，其中$\omega$=64，所以可以乱搞。

可以先用拓扑把能到达y的集合算出来，将可达性和范围限制取交集。

容易发现l≤$a_{y}$≤r可转换为$a_{y}$≥l和$a_{y}$≥r+1的异或值

现在考虑如何求$a_{y}$≥l

考虑分块，将$a_{y}$≥l分为$a_{y}$≥x·s和l≤$a_{y}$＜x·s，其中x= ⌈$\frac{l}{s}$⌉ ，s=$\sqrt{n}$

设v[x]为$a_{y}$≥x·s的集合，可直接与l≤$a_{y}$＜x·s部分取并。因为bitset比较单个元素时间复杂度为O(1)，所以l≤$a_{y}$＜x·s部分暴力计算即可

考虑修改v[x]，设在交换$a_{x}$,$a_{y}$时$a_{x}$≤$a_{y}$，将所有满足$a_{x}$＜x·s≤$a_{y}$的v[x]中删去$a_{x}$并加入$a_{y}$

将已经得到的合法y的集合设为B，求$b_{x}$的最大值。

容易想到把$b_{y}$也按值域分块，找到最大的l使$b_{y}$≥l的集合与B有交集

二分找时间复杂度接近O(nq)，肯定不行。考虑找的过程中有什么性质。

容易发现l不断增大的过程中集合元素只减不增，因此前面比较结果不变（全0才会比较下一个ull块），所以可以保留前面的比较结果。找到答案所在块后再在块内暴力比较。

修改部分与v[x]一样。

这里的比较方式比较特殊，需要手写bitset。

时间复杂度O($\frac{n(m+q)}{\omega}+q\sqrt{n}$)。