APIO2021
cunzai_zsy0531
·
2021-05-20 08:12:39
·
个人记录
Day1
决策单调性与四边形不等式-彭思进
5.19 18:30-21:00
一、定义与约定
题目中若没有明确给出，则可以认为所有 n\times m 或者 n\times n 的矩阵都可以 O(n) 预处理，O(1) 计算某个元素的值。
用 \min_i(A) 表示矩阵 A 的第 i 行的最小值在哪一位取到（相同的话取最左边的）。
定义一个 n\times m 的矩阵 A 为单调矩阵，当且仅当对于任意 1\leq i<j\leq n ，\min_i(A)\leq \min_j(A) 。
定义一个 n\times m 的矩阵 A 的子矩阵为 A_{l_1\ldots r_1,l_2\ldots r_2} ，其中 1\leq l_1\leq r_1\leq n,1\leq l_2\leq r_2\leq m 。
定义一个 n\times m 的矩阵 A 为完全单调矩阵，当且仅当 A 的每个子矩阵都是单调矩阵。
二、四边形不等式
（1）定义
称一个矩阵 A 满足四边形不等式（或称作蒙日阵），当且仅当对于任意 1\leq i_1\leq i_2\leq n,1\leq j_1\leq j_2\leq m ，有 A_{i_1,j_1}+A_{i_2,j_2}\leq A_{i_1,j_2}+A_{i_2,j_1} 。
（2）定理一
若 A 满足四边形不等式，则 A 与 A^T （A 的转置）都是完全单调矩阵。
引理：若 A 满足四边形不等式，则对 A 的任意一行或一列加入一个常数 c ，其仍然满足四边形不等式。
（3）应用一
对于一个动态规划方程 f_{i,j}=\min_{1\leq k<j} f_{i-1,k}+w_{k,j} ，考虑从 f_{i-1} 转移到 f_i 的过程可以构造一个矩阵 A ，使得
\begin{aligned}
f_{i-1,y}+w_{y,x} &,x>y\\
\infty&,x\leq y
\end{aligned}
\right.
则 f_{i,x}=A_{x,\min_x(A)} 。
对于这种，要求满足 f_i 只需要知道 f_{i-1} 的方程的问题称为满足离线决策单调性。
（4）应用二
对于动态规划方程 f_i=\min_{1\leq j<i}f_j+w_{j,i} ，可以类似地构造一个矩阵 A ，使得
\begin{aligned}
f_y+w_{y,x}&,x>y\\
\infty&,x\leq y
\end{aligned}
\right.
但是在这个问题中，可以发现，想要求出 f_i 的值，必须要知道 f_{1\ldots i-1} 。这样的问题成为满足在线决策单调性。
（5）算法一：暴力分治
设 solve(l,r,L,R) 表示当前计算 l 至 r 行，这些行的最小值在 L 至 R 列中。暴力枚举第 mid 行，求出 \min_{mid}(A) ，这样可以把原问题化为两个子问题 solve(l,mid,L,\min_{mid}(A)) 与 solve(mid+1,r,\min_{mid}(A),R) 。
考虑这样分治的复杂度，每一列至多会被扫分治深度次，故复杂度为 O(m\log n+n) 。这个算法可以解决单调矩阵的问题，而单调矩阵求解的下界复杂度即为 O(m\log n) 。下面将会继续探讨求解完全单调矩阵问题的算法。
例一 北大集训2018Day3T3 小Z的旅行计划
设 val_{i,j} 为选择 i 到 j 的答案，由 val_{i,j}+val_{i+1,j+1}\geq val_{i+1,j}+val_{i,j+1} 和求最大值想到可以把边权全部取反，这样就满足了四边形不等式。而 val_{i,j} 可以通过 \operatorname{set} 动态维护 \{p_i,\ldots,p_j\} 的dfs序来 O(\log n) 得出，直接运用上边的方法可以 O(kn \log^2 n) 解决问题。
（6）算法二：二分栈
首先探讨完全单调矩阵的性质：
性质一 对于任意两列 1\leq i<j\leq m ，一定存在一个位置 p_{i,j} ，使得对于所有的 1\leq k\leq p_{i,j} ，有 A_{k,i}<A_{k,j} ；对于所有的 p_{i,j}<k\leq n ，有 A_{k,i}\geq A_{k,j} 。
性质二 由性质一可以得出，A_{1\ldots p_{i,j},j} 和 A_{p_{i,j}+1\ldots n,i} 都一定不可能是最优的，称其为“冗余”的。
通过上面两个性质，可以得到，如果现在考虑每一列，那么每一列应该都会占据一段区间，并且列从左到右占据的区间应该也是从上到下，并且不交的。于是可以想到开一个栈来存储这个东西，加入新的一列 k 时，暴力找栈顶的列 t 占领的区间最上端 l_t ，如果 A_{l_t,t}\geq A_{l_t,k} ，那么 t 这整个一列都会冗余，直接删除。一直弹栈直到栈空或者找到一个 t 使得 A_{l_t,t}<A_{l_t,k} ，那么可以在这个 t 的区域 [l_t,r_t] 中二分找到 p_{t,k} ，从而确定 k 列占领的区间，入栈。
考虑这个算法的复杂度：每列都至多会被入栈出栈一次，每列入栈的时候至多会二分一次。所以复杂度是 O(m\log n) 的。
（7）算法三：SMAWK算法
首先是这样一个操作 reduce(A)，它表示对一个 n\times m 的矩阵进行如下操作之后，变为一个 n\times \min(n,m) 的矩阵：
维护一个 k\times k 的子矩阵，其中对角线元素 A_{i,i} 以上的所有元素都是冗余的。如果现在已经维护了一个这样的矩阵，考虑加入第 k+1 列：
如果 A_{k,k}\geq A_{k,k+1} ，则第 k 列冗余，直接删除；如果 A_{k,k}<A_{k,k+1} ，那么如果 k+1\leq n ，把后面那一列加入。
SMAWK算法的分治过程是这样的：
对于 SMAWK(A)：
计算 B=reduce(A),C=B 的所有偶数行组成的子矩阵；
递归计算 SMAWK(C)；
通过计算出来的偶数行答案去暴力计算奇数行答案，这一步复杂度大概是 O(m) 。
考虑整个算法的时间复杂度递推式 f 是
\begin{aligned}
f(\frac{n}2,n)+O(n+m)&,n\leq m\\
f(\frac{n}2,m)+O(n+m)&,n>m\\
\end{aligned}
\right.
当 n>m 时，递归 \log \frac{n}{m} 次会进入 n\leq m 的情况，上面的情况是 O(n+m) ，所以总的时间复杂度是 O(m(1+\log \frac{n}{m})+n) 。
三、二维决策单调性
（1）例一：石子合并
简单的区间dp，递推式为
\begin{aligned}
0&,i>j\\
w_{i,j}+\min_{i\leq k<j}f_{i,k}+f_{k+1,j}&,i\leq j
\end{aligned}
\right.
朴素的计算是 O(n^3) 的，现在考虑利用决策单调性来优化这个过程。
（2）朴素二维动态规划的决策单调性优化
定理一：上式中 \{w_{i,j}\} 满足四边形不等式，且 w_{i,j} 满足区间单调性，则 \{f_{i,j}\} 也满足四边形不等式。
证明需要归纳法，先归纳证明 i'=j 时的三角形不等式，再归纳证明四边形情况下的不等式。
定理二：设 f_{i,j} 最小的最优决策点为 K_{i,j} ，则有 K_{i-1,j}\leq K_{i,j}\leq K_{i,j+1} 。
如果两维都满足单调性，那么对于区间长度相同的区间都可以 O(n) 计算，总复杂度 O(n^2) ，并且拥有较小常数。
四、决策单调性最短路问题
（1）例二：环上邮局 NFLSOJ216（IOI2000邮局 加强版）
做法一：枚举每个位置断环成链，暴力 O(n^2k) 。
通过上面的暴力做法，可以发现，最优方案一定会把这 n 个物品划分成 P 个区间，每个区间去同一个邮局，处理一下前缀和就可以 O(1) 求了。
定理（答案凸性） 设 f(k) 表示 1\ldots n 经过 k 条边的最短路，则其为下凸函数。
引理 对于任意 1\leq s<r<t\leq n-1 ，都有 f(s)+f(t)\geq f(r)+f(s+t-r) 。
证明大概是对于任意的 s,r,t 构造一组特解满足？然后证明引理之后带个数进去就可以证明定理了。
这样可以考虑 wqs 二分，大概是二分一个斜率去找切点？直接做可以做到 O(n^2 \log V) 。
另外两个定理：
路径单调性定理：若存在决策单调性，设经过 k 条边字典序最小的最短路的边集为 f(p) ，若两条路径的起点和终点 s_1<s_2,t_1<t_2 ，则经过的点 s_i,t_i 都有单调性，即 s_i<t_i 。
路径不交定理：起点和终点均为 1 和 n 的路径，f(p) 与 f(p+1) 的路径不交，即 f(p+1)_i< f(p)_i\leq f(p+1)_{i+1} 。
运用上述定理可以先把例二中的村庄分成 k 个区间，找一个最小的区间仅枚举这个区间的位置断环成链，复杂度 O(nk\times \frac{n}{k})=O(n^2) 。
再次考虑分治 solve(l_1,r_1,\ldots,l_k,r_k) ，每一层跑一个 Wilber 或者 SMAWK 算法或者二分栈和分治，并且每次把最小的区间转到最前面做，复杂度 O(n(\log n+\log V)) 或 O(n\log n(\log n+\log V)) 。
五、四边形不等式的其他应用
（1）生成随机蒙日阵
如果 C,D 是蒙日阵，则 C+D,\lambda C,C^T 都是蒙日阵。故可以找几个常见蒙日阵，随机运算一下就差不多了。
还有另外一个方法是使用次模函数构造蒙日阵。次模函数的定义是：设 E 是一个有限集合，定义在幂集 2^E 的实函数 f ，对于任意的 X,Y\in E ，均满足 f(X)+f(Y)\geq f(X\cap Y)+f(X\cup Y) ，则 f 为次模函数。
后面还有一些使用决策单调性解决旅行商问题的讲解？？？反正彻底下线啦。
Day 2
Open Cup 趣题选讲-蒋凌宇
2021.5.20 18:30-21:00
一、Open Cup简介
Open Cup是对世界各地举行的一些质量比较高的算法竞赛的题目的收集。比如 Pretrozavodsk Camp，EC-Final，Moscow Workshop，还有一些不太知名的比赛的题。整体难度较大，申请账号门槛高，但是可以在 codeforces 上一位名叫 zimpha 的人的博客里看题。
二、题目选讲
T1 Cactus Competition
XXI Open Cup.Grand Prix of Korea,Problem B
题意：给定一张 n\times m 的网格图，(i,j) 的权值为 A_i+B_j ，其中 A,B 都是给定的序列。求有多少对 (S,T)(1\leq S\leq T\leq n) ，满足存在一条 (S,1) 到 (T,m) 的路径，每一步只能向下或向右走一步，并且只能经过权值非负的格子。
题解：首先考虑 $1-n$ 的情况。如果以下条件都不满足，则一定存在路径：
1. 有一行不能走。即存在 $1\leq i\leq n$，对于任意 $1\leq j\leq m$，都有 $A_i+B_j<0$；
2. 有一列不能走，式子与上边类似。
3. 有一个不能走的框把起点框起来了。即存在$1\leq x\leq n,1\leq y\leq m$，使得对于任意 $1\leq i<x$ 都有 $A_i+B_y<0$，且对于任意 $1\leq i<y$ 都有 $A_x+B_i<0$。
4. 有一个不能走的框把终点框起来了。式子与3类似。
证明充要的方法大概是，构造一个从起点走到终点的路径。先选择一个中间点，然后分别对两个子问题进行考虑，用第 $3$ 和第 $4$ 个性质反证子问题一定成立，则结论一定成立。
接下来考虑四个性质对 $(S,T)$ 的影响，前两个性质就是把大问题分成两个子问题。后两个性质的影响可以用单调栈+二分求出，最后的复杂度是 $O(n\log n+m)$。
**T2 Query On A Tree 17**
XXI Open Cup.Grand Prix of Korea,Problem I
题意：给一个 $n$ 个点的有根树，初始点权为 $0$。有 $q$ 次操作，每次会将某个点 $u$ 子树内所有顶点点权 $+1$ 或者将 $u$ 到 $v$ 路径上点权 $+1$，求一个点 $v$ 使得 $\sum_{1\leq u\leq n}A_u\cdot dis(u,v)$ 最小。
题解：若点权和为 $S$，则最浅的带权重心的子树点权和一定大于 $\frac{S}2$。所以如果将所有顶点按照dfs序写下来，每个点写这个点的点权次，那么这个序列的最中间的点一定在答案点的子树中。于是可以用重链剖分加线段树来维护点权和，注意到重链剖分也是一个dfs序，于是每次查询可以在线段树上二分找到中间点，然后直接在这个点到根节点的路径上找最优点就行，这个过程可以用倍增解决。每一次可以 $check$ 一下这个点要不要跳，具体方式大概是在线段树上查子树和一类。这样做总复杂度是 $O(n+q\log^2 n)$。
**T3 Steel Slizing 2**
XXI Open Cup.Grand Prix of Korea,Problem L
题意：平面上有一个多边形，长度为 $n$，第 $i$ 个位置的高度为 $h_i$。需要切最少的次数使每个部分都是矩形。切的每一刀只能跟多边形有两个交点，并且在多边形内部。切掉之后的图形不能一起切。$n\leq 2.5\times 10^5$。
题解：最后每一块都是矩形相当于是凹顶点（$270$ 度的顶点）个数为 $0$。切一次只会把凹顶点数目 $-1$ 或者 $-2$，问题转化为最大化 $-2$ 次数。
竖着的情况可以直接求，如果上下都是凹顶点就行。横着的情况相当于是需要满足两个位置的横坐标相等，且这两个位置中间的任何位置都比它们要高。这个问题大概可以用笛卡尔树求得。
现在得到了一些横着和竖着的边。如果有两条边相交，那么它们只能选一个，这是一个二分图最大独立集问题，它等于边数减去最大匹配。考虑到这个题的边有特殊性质，横着的一定是向一个区间连边。这时候不要直接线段树优化建图跑网络流啊……可以直接跑一个贪心的类似区间覆盖的东西，用堆维护一下。复杂度 $O(n\log n)$。
**T4 Interesting Drug**
XXI Open Cup.Grand Prix of Korea,Problem K
题意：有 $n$ 件物品排成一行，一个人可以左右移动，走到了一个地方，如果有物品就会拿。对于第 $i$ 个物品，如果这个人第 $C_i$ 个取走它，会得到$D_i$ 的收益，否则没有任何收益。对于每个 $1\leq i\leq n$，求初始位置为 $i$ 时能够取得的最大收益。$n\leq 3\times 10^5,1\leq D_i\leq 10^9$。
题解：倒过来考虑，记 $(L,R)$ 表示现在拿了 $[L,R]$ 的物品。此时需要扔掉位置为 $L$ 或 $R$ 的物品，最后就到 $(i,i)$，这样复杂度是 $O(n^2)$。考虑有贡献的边只有 $(i,i+C_i-1)\rightarrow (i+1,i+C_i-1)$ 和 $(i-C_i+1,i)\rightarrow (i-C_i+1,i-1)$。这样的点的个数是 $O(n)$ 的。考虑把它们放到二维平面上，贡献相当于就是一个二位偏序，树状数组维护DP即可。复杂度 $O(n\log n)$。
**T5 Find the LCA**
XXI Open Cup.Grand Prix of Tokyo Problem F
题意：给定 $A_1,\ldots,A_n$，考虑所有 $n$ 个点组成的有根树，其中第 $i(2\leq i\leq n)$ 的父亲是 $p_i(1\leq p_i<i)$，点权为 $A_i$。一棵树的分数为顶点 $LCA(n-1,n)$ 的子树内所有顶点点权的乘积，求所有 $(n-1)!$ 种树的分数和，$\mod 998244353$。$n\leq 2.5\times 10^5,7s$。
题解：考虑 $lca(n-1,n)$ 的子树集合为 $S$ 的方案数。显然，如果 $lca(n-1,n)=1$，那么 $S=\{1,2,\ldots,n\}$，方案数是???；如果不是，那么方案数为 $(n-|S|-1)\cdot (\min S+1)$。现在考虑 $lca(n-1,n)=1$ 的答案种类，事实上它是所有情况的一半，即 $\frac{(n-1)!}{2}$。为什么会这样呢？现在考虑构造双射证明。
构造双射证明说的是，从两个问题集合中构造一组一一映射，如果能构造出来，说明这两个问题是等价的，或者集合大小是相同的。首先考虑从 $gcd(n-1,n)=x(x\neq 1)$ 映射到 $gcd(n-1,n)=1$ 的方案：将 $x$ 的子树中含有 $n$ 的节点接到 $p_x$ 上，然后把 $x$ 和剩下的子树接到 $1$ 上；然后从 $gcd(n-1,n)=1$ 映射到 $gcd(n-1,n)=x(x\neq 1)$：直接将 $x$ 和它的子树插入 $n$ 到根的路径上，因为要满足父亲的编号比儿子小，所以插入的位置是唯一的。这样就证明了 $lca(n-1,n)=1$ 的树一共有 $\frac{(n-1)!}{2}$ 种。
然后对于 $lca(n-1,n)\neq 1$ 的情况，大概要求一个这样的式子：
$$\sum_{S\subset\{2,3,\ldots,n\},|S|=k}\min (S)\cdot \prod_{i\in S} (1+A_i)$$
普通的分治FFT说的是，考虑一些多项式的乘积，把它从中间分开，分别计算出左边右边的答案，然后FFT乘起来，复杂度是 $O(n\log^2 n)$。这个式子的分治不太一样，大概说的是有很多多项式的乘积求和。这样也可以分治，画一个图可以发现，对于 $[l,mid]$ 的需要卷上一个右边的多项式乘积，对于 $[mid+1,r]$ 的直接加到答案里即可。复杂度还是 $O(n\log^2 n)$。
**T6 Japanese Knowledge**
题意：有一个非降正整数序列 $A_{1\ldots n}$。对于每个 $0\leq k\leq n$，求满足以下条件的非降非负整数序列 $x_{1\ldots n}$ 的数量 $\mod 998244353$：
1. $x_i\leq A_i(1\leq i\leq n)$；
2. 恰好有 $k$ 个位置满足 $x_i=A_i$。
$n\leq 2.5\times 10^5,1\leq A_i\leq 10^5,10s$。
题解：考虑 $A$ 数组相当于是在平面上给出了一个区域，其中第 $i$ 个位置的高度是 $A_i$，现在实际上是求只能在区域内部走，从左下到右上的方案数。
首先考虑如果没有 $k$ 的限制，那么可以分治 FFT 解决。如果满足 $k$ 组 $x_i=A_i$，发现这个问题的答案等价于 $f(A_{k+1}-1,A_{k+2}-1,\ldots,A_n-1)$。证明仍然考虑构造双射，从原问题去掉所有 $x_i=A_i$ 的位置可以映射到新问题，新问题大概是插入到最前面的大于它的位置映射到原问题？然后就可以分治 FFT 并且在过程中统计答案。复杂度 $O(n\log^2 n)$。
**T7** 没讲。
**T8 Chess Tournament**
XXI Open Cup.Grand Prix of Samara,Problem I
题意：$n$ 位选手两两进行一次比赛，每轮至多 $k$ 对（$2k$ 位选手互不相同）同时比赛，设计一个总轮数最少的方案。$n\leq 200,1\leq k\leq \frac{n}2$。
题解：首先考虑 $k=\frac{n}2$ 的情况：
若 $n$ 为奇数，第 $k$ 轮令 $i+j\equiv k\pmod n$ 的 $i$ 和 $j$ 进行比赛，每一轮都有一个人和自己比（轮空）。
若 $n$ 为偶数，上面那个方案中每一轮剩下的人肯定都不一样，那个人和 $n$ 比赛。
因为两种情况都达到了下界，所以一定是最优的。
现在考虑 $k<\frac{n}2$ 的情况，先将上面的方案按照轮和编号从小到大的顺序写下来（$n$ 为偶数时，先写 $(i,n)$），注意到每个人在两轮之间的位置至多改变 $1$，故同一个人不会在连续 $\frac{n}2-1$ 场比赛中出现两次，所以直接连续 $k$ 场比赛一轮即可在达到下界的同时满足题目条件。
完结撒花！谢谢朋友们！