证明_LCA

证明

排序问题 值域压缩原理

常见的值域压缩是离散化，但更加强力的值域压缩是枚举中值，然后把序列变成 $0/1/-1$。

---

$0/1$ 序列逆序对数，相当于 $0$ 看成向右走，$1$ 看成向上走，那么逆序对数相当于折线右下方面积。

例：每次找到相邻 $0/1$ 逆序对交换，相当于每个”角“消失，所以次数就是右下角向左向上走的最大次数，以右下角为原点则答案为 $\max(x+y)$。

例：正向冒泡排序再反向冒泡排序，等价于每次削掉最外面一层，答案是 $\max(\min(x,y))$，P4375 就是原序列是正常排列

介值定理

思考题：

有n个物品，每个物品有重量wi和体积vi且密度均匀。你可以切物品，每次可以选一个物品切成两部分，也就是选一个0到1的实数k把物品分成k和(1-k)比例的两个物品。

你有最多X次切的机会。

问题1. 要想保证切完之后一定能把物品分成两组使得两组重量和相等，体积和也相等，X至少是几。

问题2. 设计高效算法求问题1的方案。

问题3. 如果是分成三组呢

问题0. 如果是要把物品分成两组使得两组数量相同且体积和也相等呢（不考虑重量）。

1,2 是沙东省集出过的题，之前的分析方法是每个物品看作矩形，长为体积宽为密度面积为重量，按照宽排序排列在 $x$ 轴上，相当于要选 $x$ 轴长为 $\sum x/2$ 的区间，总面积是总面积的一半，滑动窗口介值定理即可。

三组同理，可以证明是四刀，四刀以下想卡掉只需要两个人重量大于 $\frac 1 3$ 总重量，两个人体积大于 $\frac 1 3$ 总体积，这样四个人都不得不切。

其他理解方式：

• 在圆环上排列物品，旋转直径来分组，$f(\theta)=-f(\theta+\pi)$，介值定理可证，三等分可以用平均值定理，三个中的最大值 $\ge \frac 1 3$ 全部，最小值同理。
• 把选一个物品看作向量加 $(w,v)$，于是相当于我们要过 $(\sum w/2,\sum v/2)$，观察发现切两刀相邻的两个元素，等价于它们的相接点是两人构成的平行四边形中的任意一点，于是相当于我们要找到一种方式使得最靠近中点的两个向量张成的平行四边形包含中心点。
  • 考虑先搞一个斜率倒序排列，再随意地将相邻逆序对交换，你发现总有一个时刻中心点被包含，这是二维的介值定理。

问题 0：尝试证明奇数一刀偶数两刀。

偶数两刀可以用圆环旋转直径来证，也可以直接规约到奇数一刀。

奇数一刀等价于中心物品跨过中点，考虑先排序，再不断将最后一个物品挪到最前面，这显然取到了两种极端情况，并且每次变化量 $\le 1$。

另一种证明方式是排序，将 $a_2-a_1,a_4-a_3,\cdots$ 视为一些可以添加正负号的物品，显然得证。

理解起来较为困难的例子：

二维平面上有n个点，要求这些点互相不重合，并且三点不共线，编号为1…n，现在我们要画一条直线，如果一个点(x,y)满足Ax+By+C>=0，则视为点(x,y)在直线Ax+By+C=0的上方。将直线上方的点看做是一个集合。

问题1.如果n个点的坐标由你来构造，对直线Ax+By+C=0，假设A,B,C取遍所有实数，最多可以得到多少个不同的集合

问题2.如果有若干条直线，其上方点的集合相同，是否可以通过对这些直线进行旋转和平移，使得这些直线变成同一条直线

问题3.如果改变你在问题1中构造的点的坐标，不同的集合数是否会发生改变

问题4.给定点(x,y)，对于所有过(x,y)的直线，是否一定存在一条直线，使得直线两侧的点数最多只差1，这里的点数不统计(x,y)，如果点在直线上，由你决定属于哪一侧

问题5.是否可以找到两条相交的直线，使得给定的n个点被分成四个点集，且最大的点集和最小的点集大小最多差1，如果点在直线上，由你决定属于哪一个点集

问题6.是否可以找到三条共点的直线，使得给定的n个点被分成六个点集，且最大的点集和最小的点集大小最多差1，如果点在直线上，由你决定属于哪一个点集

问题 2：考虑尽可能地绕线上任何点逆时针旋转这条线，使其卡在两个点上。

问题 5 的构造方案：先找到一个二等分线，再保证其中一边二等分，称第二条线为线 2，设角度为 $\theta$ 的线 2 为 $f(\theta)$，容易发现 $\theta$ 取极端值的时候，另一边的点数从 $0$ 到 $\frac n 2$ 都取到了。

问题 5 连续性的证明：考虑利用问题 $2$ 的变化是连续的，仅考虑我们要求二等分的那一边的所有点，先将其尽可能地旋转使其卡在这一边的两个点上，然后交换这两个点所属的部分，然后你发现可以接着转了。

问题 6 的构造方案：先确定一条二等分线，我们可以利用问题 5 的方法构造出一条 $\frac 1 6$ 的直线，设问题 5 方法的映射是 $f$，考虑把第三条线绕着两线的交点旋转，直到我们已经分出了 $4\times \frac 1 6$，剩下的两边没确定。

接下来我们将前两条线方向取反，画一下图可以发现第三条线与第一条线在另一边的夹角，一次大于 $\frac 1 6$，另一次小于 $\frac 1 6$。

问题 6 的连续性：考虑转第一条线直到卡到两个点，接下来转第二条线直到卡到两个第一条线异侧的点（如果是同侧的点就交换所在部分），然后同时交换四个点所在部分，于是可以继续转。

区间问题

区间最大子段和

区间最大子段和问题：给定一个长为 $n$ 的整数列 $\{a_i\}$（有正有负），每次查询一个区间，问这个区间的所有子区间中，区间和最大的是多少。

问题1. 如果有一种修改是全局加同一个数，且只有全局查询，如何维护。（考虑，所有可能的答案区间有哪些？）

问题2. 如果有一种修改是全局加同一个数，且所有询问区间都是后缀（右端点都是 $n$），如何维护。

问题3. 给定一个长为 $n$ 的整数列 $\{a_i\}$（有正有负），求出每个后缀的平均值最小的前缀。【ABC341G】

问题4. 给定一个长为 $n$ 的整数列 $\{a_i\}$（有正有负），区间加，区间查询平均值最小且长度不小于 $k(k\le 10)$ 的子区间。

问题5. 区间加正数，区间最大子段和。（考虑能否用组合方法证明复杂度？）【P5693】

区间加，求可能成为最大子段和的区间

只有 $\mathcal O(n)$ 个，可以建树，基于以下两点：

• 当前时刻可能的区间，下一时刻也可能。
• 两个区间有交则可以合并成为更大的区间，所以所有极大可能区间要么不交要么包含。

最初时最优区间是，每两个数之间的一个空区间。

---

思考题：连续段

有一个 $n$ 阶排列 ${a_i}$，定义 $f([l,r])=[\min(a_l,\dots ,a_r), \max(a_l, \dots, a_r)]$。

问题：对一个初始区间不断迭代 $[l,r], f([l,r]), f(f([l,r])),\dots$，如何刻画这个过程。

问题1. 对输入的 $[l,r]$，设计一个尽可能高效的算法判定多次迭代 $f$ 能否达到 $[1,n]$

问题2. 对输入的 $[l,r]$，如果可以迭代达到 $[1,n]$，设计算法求出最少需要迭代 $f$ 多少次。（CF1707E）

问题3. 对任意一个 $[l,r]$，不断迭代 $f$ 可达到的不同区间个数的（渐进）上界是多少？（也是上个问题答案的上界）

问题4. 如果给定的 $a$ 不是排列，而是一个值域 $1$ 到 $n$ 的数组，数值可以重复出现，问题3的答案会有变化吗？（CF1707E）

问题5. 如果多次区间询问有多少个子区间可以在有限步内迭代到 $[1,n]$，能做吗？

问题6. 如果多次区间询问有多少个子区间可以在有限步内迭代回到自身，能做吗？