## 伸展
#二分 #数学 #前缀和 #后缀和
首先答案是可以二分的，当 $K$ 达到比所有的相邻 $a$ 的差值都要大的时候那么 $K$ 绝对是满足条件的，而如果一个 $K$ 满足条件那么 $K+1$ 也是满足的，因此可以二分答案 $K$ 值。
考虑如何判断 $K$ 是否满足条件。令 $p$ 表示为当前线段的左端点，那么很显然最开始时 $p=l$ 是最优的。接下来枚举 $i\in [l,r]$，判断能否伸到当前的点，即判断 $p+K\ge a_i$，如果不满足可以直接返回不满足条件；否则令 $p\gets \min(p+K,a_{i+1})$，也就是往右铺 $K$ 的长度，但是要保证下一个点仍然可以被覆盖。
时间复杂度 $\mathcal O(Qn\log_2 V)$，可以通过 $50$ 分。由于有多组询问，可以尝试整体二分，但是由于我整体二分的 check 没有写好导致复杂度和正常二分是一样的。
因此我们需要找出规律。把上一个 $p$ 的值带入进去，拆开 $\min$，就可以得到 $r-l+1$ 个不等式：
$
\begin{cases}
a_l+K\ge a_l \\
\min(a_l+K,a_{l+1})+K=\min(a_l+2K,a_{l+1}+K)\ge a_{l+1} \\
\min(\min(a_l+K,a_{l+1})+K,a_{l+2})+K=\min(a_l+3K,a_{l+1}+2K,a_{l+2}+K)\ge a_{l+2} \\
\cdots
\end{cases}
$
对于第 $i$ 个不等式，它描述了从 $l$ 开始能否走到 $l+i-1$。多个数的 $\min$ 值大于等于一个值，那么这每一个数都要大于等于那个数，以第三个式子举例
$
\begin{cases}
a_l+3K\ge a_{l+2} \\
a_{l+1}+2K\ge a_{l+2} \\
a_{l+2}+K\ge a_{l+2}
\end{cases}
$
准确地来说，对于从 $l$ 开始走的情况，如果最终要走到 $r$，它的必要条件是对于 $i\in[l,r]$，有 $a_i+(r-i+1)K\ge a_r$，由于 $K$ 是整数解方程得到 $K\ge\left\lceil\cfrac{a_r-a_i}{r-i+1}\right\rceil$。因此 $K$ 最终的取值是 $K=\max\limits_{i=l}^r\left(\left\lceil\cfrac{a_r-a_i}{r-i+1}\right\rceil\right)$。
当所有必要条件都满足（$l$ 到 $l+1$ 能走通，$l$ 到 $l+2$ 能走通，……，$l$ 到 $r$ 能走通）时，$l$ 到 $r$ 才是真正可以走通的，因此 $K$ 要是所有 $l$ 到 $i$ $(i\in[l,r])$ 要求的 $K$ 值的最小值中的最大值。也就是最终 $l$ 到 $r$ 的答案等于
$
\max_{i=l}^r\max_{j=l}^r\left(\left\lceil\cfrac{a_i-a_j}{i-j+1}\right\rceil\right)
$
做两遍后、前缀 $\max$ 即可，也可以一遍搞完。时间复杂度 $\mathcal O(n^2+q)$。
```cpp
#include <iostream>
#include <cmath>
using namespace std;
using LL = long long;
const LL kMaxN = 5005;
LL a[kMaxN], ans[kMaxN][kMaxN], n, q;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
for (LL r = n; r >= 1; r--) {
for (LL l = r - 1; l >= 1; l--) {
ans[l][r] = max(ans[l + 1][r], (a[r] - a[l] + r - l) / (r - l + 1));
}
}
for (LL l = 1; l <= n; l++) {
for (LL r = l + 1; r <= n; r++) {
ans[l][r] = max(ans[l][r], ans[l][r - 1]);
}
}
for (LL l, r; q; q--) {
cin >> l >> r;
cout << ans[l][r] << '\n';
}
return 0;
}
```
## 内鬼
我写的暴力。首先枚举删除的两个点，然后枚举相交的弦并累加答案。唯一有难点的是如何判断两个弦是否相交，最简单的道理是拿出其中一个弦 $(a,b)$（$a<b$，不满足就交换），另外一个弦 $(c,d)$ 其中一个属于 $(a,b)$，另外一个不属于 $(a,b)$。时间复杂度 $\mathcal O(n^2m^2)$。成功获得 $20$ 分。
## 零一
我还是写的暴力。暴力枚举左端点然后往右找右端点，加上奇妙小剪枝，时间复杂度 $\mathcal O(n^2q)$ 但是可以通过 $30$ 分。
## 反转
我分类写的暴力。对于 $n\le 18$ 的数据，猜测答案不会太大所以进行迭代加深搜索；对于 $n,m\le 3000$ 但是答案不超过 $1$ 的，先特判答案为 $0$ 然后在枚举操作的点是什么。用并查集判断连通性。成功获得 $25$ 分。
## 总结
总分：$100+20+30+25=175$。
这场比赛相对于之前还是比较良好的，虽然在第一题坐牢了三个小时但是最终还是写出来了，后面的暴力也很稳，暴力本身没有挂掉，我也没有漏掉我不会会写的子测试点。只是水平还是有限了，第二题不会容斥，无法追求更高的分数，等会讲题的时候再看看。