$1 \le n \le 10 ^ 5$

这个题要求的是第 $i$ 发导弹不能高于第 $i - 1$ 发，也就是说，我们的导弹的高度是单调不升的，我们最多能拦截的导弹怎么算呢？最少用几套系统拦截呢？

对于第一问来说，我们将视角反转过来，看从末尾开始，每次导弹的高度都要大于等于上一次的，最多能打几个，那么这就是一个简单的 LIS 问题，那么我们求的就是非严格上升的最长子序列。

对于这类问题我们采用的方式常见的就是 $\mathcal{O}(n ^ 2)$ 的 DP，但是这个题的复杂度不允许，我们用另一种形式，我们定义 $f_i$ 表示长度为 $i$ 结尾的这样的上升子序列，结尾最短的值，那么我们发现这个值在 $f$ 中一定是单调的，我们考虑维护这个 $f$ 数组。

如果当前的 $a_i > f_t$，那么说明当前的 $a_i$ 只能接到 $f$ 的后面，无法对之前的造成任何有益的贡献。

如果当前的 $a_i \le f_t$，那么说明当前的 $a_i$ 虽然不能接到 $f$ 的后面，但是可以对之前更短的 $f$ 产生一个更优的贡献，我们只需要找到第一个大于 $a_i$ 的位置的 $f_j$，直接 $f_j \to a_i$ 即可。

然后对于第二问来说，这是一个很著名的定理，叫做 **Dilworth 定理**，这个定理的内容是这样的：

对于一个偏序集 $S$ 上的偏序 $\preceq$，称 $S$ 的全序子集为 **链**。若 $S$ 的子集 $T$ 中任意两个不同的元素均不可比则我们称 $T$ 为反链。

说人话就是，现在有一个全集 $S$，从中选出若干个元素，组成一个集合，这个集合按一种特殊的偏序的关系，则这个集合 $S$ 中的任意两个元素都能进行比较，则这个子集称为**链**。若有个子集 $T$，对于这个集合中的任意选出的两个元素，都无法按照这种偏序关系比较，那么称这个子集 $T$ 为**反链**。

需要注意的是这个偏序关系 $\preceq$ 来说，其可能是一种比较方式，就是钦定的一种规则，例如，当 $a \le b$ 时我们称其为可比，那么我们拿出来的如果是 $a > b$ 就是不可比。

我们设 $(S, \preceq)$ 为一个有限偏序集，则：

- 最小链覆盖数 = 最大反链长度

- 最小反链覆盖数 = 最大链长度

那我们这个题就可以直接做了，我们对于 $\ge$ 的偏序关系来说，其反就是 $<$，就是严格的小于，那么我们求严格最长上升的长度就是答案。

$1 \le n \le 3.5 \times 10 ^ 4, 1 \le a_i \le 10 ^ 5$

题面很简约，长度为 $n$ 的整数序列 $a$，我们要保证这个东西在修改完之后是严格单调递增的，第一问问我们最少改变的数的个数。

很朴素的思路是我们先求出 LIS，再直接用 $n - l$ 就是答案，但是这样是错的，我们看这个样例：

4
1 2 2 3

对于这个来说，我们的 LIS 选出的长度显然是 $3$，就是 $\{ 1, 2, 3\}$，这样的话我们的代码误以为我们只需要对 $2$ 修改即可，但是实际上并非这样，我们的 $2$ 无法修改为 $2 \sim 3$ 中间的任何 $Z$。

那怎么办呢？我们选择 $a_i$ 和 $a_j$ 作为一对上升的序列中的一部分的条件不止 $a_i < a_j$，我们发现其还满足 $a_j - a_i \ge j - i$，我们对其移项得到 $a_j - j \ge a_i - i$，那么我们直接重标号，定义数组 $b$，使得 $b_i = a_i - i$，那么我们只需要对于这个 $b$ 求 LIS 即可，答案就是 $n - l$。

对于第二问，其要求我们在第一问的基础上，对选出的这最少的进行修改，使得修改的绝对值之和最小。

我们要把 $a$ 变成严格上升的和 $b$ 变成单调不降的修改的答案应当是一样的，我们这里做一个简单证明，对于 $a_i$ 和 $a_{i + 1}$ 来说，我们要求的是 $a_i < a_{i + 1} \rightarrow a_i + 1 \le a_{i + 1}$，而我们的 $b_{i} = a_i - i$，那么我们的 $b_i - i \le b_{i + 1} - i - 1 \rightarrow a_i + 1 \le a_{i + 1}$。好的我们已经证明了问题是等价的，那么我们去解决 $b$ 的单调不降问题即可。

接下来我们考虑这样的问题，定义集合 $T \in S$，$T$ 是其全集 $S$ 的 $\preceq$，我们现在要解决的是 $A \notin T$ 的这些应该把题面放到哪里呢？

我们考虑假设我们已经考虑好前 $i$ 个元素的答案是 $f_i$，我们现在要求你从这个 $i$ 转移到下一个 LIS 加 $1$ 的位置怎么转移。我们现在问题在于中间的 $[i + 1, j - 1]$ 的区间的点全是要么 $< b_i$ 的，要么是落在 $> b_j$ 的，如下图：

我们应当如何调整中间的 $b$ 呢？我们要求 $b$ 单调不降，那么我们至少是 $b_i \le b_{i + 1}$，我们至少需要让这些东西全落在黄色的部分。

那么如何做到最小呢，我们显然是尽可能的使其贴近边框，我们称以一个点 $k \in [i + 1, j - 1]$ 的部分，我们使得 $[i + 1, k]$ 的部分直接移动到下边框上，$[k + 1, j - 1]$ 的部分我们直接移动到上边框上，这个时候一定是有最优解的。如下图：

如何证明这个解是最优解呢，我们考虑这样的折中方案（毕竟人脑觉得很优），如下图：

我们定义这样的紫色平台中的从上方降下来的为 $Y$，从下方升上来的为 $X$，那么分为以下三中情况：

1. $X > Y$

   那么我们说，如果将所有紫色平台全部降下去，由于 $X > Y$ 的缘故，最终的 $\Delta > 0$，我们刚刚的方案是优的。

2. $X < Y$

   那么这种情况是和上面的是对称的，我们将所有平台升上去，最终的 $\Delta > 0$，所以也优。

3. $X = Y$

   这种情况在中间和两边共享最优方案。

因此，我们证明了刚刚的划分方式一定包含最优解。

那么最终的实现还是不是很好实现的，我们将上述的内容转成式子，可以得到下式：

$$dp_j = \min \{ dp_j, dp_i + \sum_{p = i + 1} ^ k |b_p - b_i| + \sum_{p = k + 1} ^ {j - 1} |b_p - b_j| \}$$

我们注意到这个式子的两个 $\sum$ 可以在每一轮直接用前后缀和预处理出来，可是你的 $i, j$ 的枚举就已经达到了 $\mathcal{O}(n ^ 2)$，怎么办呢？

我们发现很多地方的枚举是无效的，我们需要使得 $j$ 的位置的结尾的 LIS 长度恰好为 $i$ 位置为结尾的 LIS 的长度 $+1$，那么我们直接开一个 vector 来记录长度为 $i$ 的下标的下标集合，这样我们枚举 $j$，只需要从 $l_j - 1$ 的长度的下标的地方转移，这是一个很大的优化。因为随机数据下 LIS 长度的期望是 $\mathcal{O}(\sqrt{n})$，那么实际上我们最终的复杂度期望在 $\mathcal{O}(n \sqrt{n})$ 左右，对于 $3.5 \times 10 ^ 4$ 的数据也是轻松通过。

$1 \le n \le 1000, 1 \le m \le 200, 1 \le k \le m$

我们发现 $A$ 的 $k$ 个子串拼接的 $S$，且 $S = B$ 的方案数。

我们定义这样的方案，我们发现这个子串的拼接方式是这样的：

1. 直接接到上次的子串后面

2. 单开一个新的子串

我们定义这样的状态，$f[i][j][k]$ 表示必须选择 $i$ 这个点，已经选择出来了 $k$ 个子串，能与 $B$ 的前 $j$ 个字符相匹配，定义 $g[i][j][k]$ 表示选或不选 $i$ 这个位置，剩下和 $f$ 的定义一样的方案数。

那么我们的转移是这样的：

- 当 $A_i = B_j$ 的时候

 那么 $f[i][j][k] = (f[i - 1][j - 1][k] + g[i - 1][j - 1][k - 1])$，这个东西就是，要么你拼接在后面，要么你单开一个，造成新的 $k$ 的贡献。我们的 $g[i][j][k] = (g[i][j][k] + f[i - 1][j][k])$，这个东西就是你不选 $i$ 的和上一次的。

- 当 $A_i \ne B_j$ 的时候

 那么我们的 $f[i][j][k] = 0$，我们的 $g[i][j][k] = g[i- 1][j][k]$。

但是我发现此时的空间超限，我们发现每次的 $i$ 只从 $i - 1$ 转移，于是我们很愉快的滚动数组优化一下即可。或者倒序枚举。

$1 \le T \le 3 \times 10^5, 0 \le M \le 10^3, 1 \le S \le 10^8$

我们发现什么时候去做跳跃其实是并不重要的，我们只需要知道的是，对于当前的时间来说，我们定义 $f_i$ 表示，到当前为止，第 $i$ 秒，所能走的最远距离，我们先预处理出来 $p_j$ 表示 $j$ 秒纯法术能达到的最远的距离，我们 DP 的时候就直接转移，我们直接省事一些就可以对纯法术的这个 $p$ 数组直接操作，我们转移式子如下 $p_i = \max\{p_{i - 1} + 17, p_i\}$，这样就完美的做到了转移，按最优的结构转移，因为你当前的操作在这样的处理下是没有后效性的。

$n \le 100$

这个题很简单了，但是如果我们的 $n \to 10 ^ 5$ 呢？我们依旧可以做，只需要做两遍 $\mathcal{O}(n \log n)$ 的 LIS，最终统计答案的时候将答案拼起来即可。注意拼答案的时候枚举的中点也是一个人。

千篇一律的矩形数点看腻了？来点纯的 DS 做法。

前置知识：ST 表，单调队列。

和题目一致，用 $k_i$ 表示当前询问下 $i$ 的答案。

利用特殊性质，由此能够导出两个优化的方向。

解法 1

考虑特殊性质 $D$：$L_j> \frac{n}{2}$。

特殊性质 D $O(nq)/O(nq+n\log n)$

在分治方向上思考，不难发现，特殊性质等价于：任意合法的区间一定经过序列的中点。

标记序列中点 $mid$，对于序列左半边的一个点 $i$，不难发现，设 $f_j$ 表示以 $j$ 为左端点的最大权值合法区间 $[j,r]$，只需要满足 $j\le i$，则一定有 $j\le i\le mid< r$。

所以说，对于左半侧的位置 $i$ 的答案，只需要对于每个 $j\in [1,mid]$ 求出对应的 $f_j$，则 $k_i=\max_{j\le i}f_j$。

求出 $f_j$ 可以用滑动窗口（或者 ST 表，后者常数应该更小），$k_i$ 直接统计前缀最大值，比较容易可以做到 $O(nq)/O(n\log n+nq)$。

一般情况 $O(nq\log n)$

考虑拓展这个做法：

上述做法中，我们不关注合法区间的长度，所需要的条件只是合法区间必须经过序列中点。

考虑分治，对于当前分治区间，只保留经过区间中点的合法区间，没经过的则丢到两边分别做分治，每个分治区间里都做一遍上述算法，可以做到复杂度 $O(nq\log n)$。

根据常数可以获得 $50\sim 70$ 分不等。

一般情况 $O(nq+n\log^2 n)$

继续优化：

对于区间 $[l,r]$，处理询问 $[L,R]$，有一些显然的事实：

1. 计算 $[l,r]$ 经过中点的代价为 $O(\min(R,r-l+1))$。

2. 若 $r-l+1<L$，则区间没有计算和分治的必要。

设最大的 $\frac{n}{2^t}\le L$，则根据事实二，分治最大进行到第 $t$ 层。分治的区间个数量级为 $\sum_{h=0}^t 2^h \approx 2^{t+1}> \frac{n}{L}$。

根据事实一，我们分治算法的时间复杂度的一个下界为 $O\left(qn\frac{R}{L}\right)$。

看出来了什么？当 $R,L$ 之间的比值太大时，复杂度中 $qn$ 的系数退化就会变成 $\log n$，这是我们不希望的。我们希望的是 $O\left(\frac{R}{L}\right)\approx O(1)$。

另外一个显然的事实：对于询问 $[L,R]$，可以拆成 $[L,p],[p+1,R]$ 两个询问来处理。

考虑这样一种倍增分块的方法：对于 $t\in [0,\log n)$，我们将 $R-L+1\le [2^t,2^{t+1})$ 分为一块，只有 $\log$ 块，合法区间长度在这些块的询问可以预处理！

对于一次询问，考虑去掉中间的整块部分，剩下的散块一定满足存在一个 $t$，使得 $2^t\le L\le R< 2^{t+1}$，这样的散块直接做分治的复杂度就是 $O(n)$！

预处理做 $O(\log n)$ 次分治，然后预处理 $G_{i,j,k}$ 表示询问长度在 $i\sim j$ 块内位置 $k$ 的答案，这一部分可以做到 $O(n\log^2 n)$。

每次查询，整块直接统计答案，散块直接做两个线性的分治，复杂度为 $O(nq)$。

于是我们在 $O(n\log^2 n+nq)$ 的复杂度内解决这个问题，虽然常数比较大，但这种线性分治的思想非常巧妙。

解法 2

这次变换视角，我们根据特殊性质 D 转化出一个关键的条件：$2L_j>R_j$。

特殊性质 D $O(nq)/O(nq+n\log n)$

观察这个条件，可以注意到另外一个关键的结论：对于覆盖 $i$ 的最优合法区间 $[l,r]$，一定有 $i$ 到左右两个端点的最小距离一定不超过 $L$。

对于 $k_i$，考虑枚举一个和 $i$ 距离不超过 $L$ 的左端点 $j$，计算以 $f_j$ 为左端点的最大合法区间 $[j,r]$，因为 $r-j>L,i-j<L$，所以一定有 $i\le r$。

因此覆盖 $i$ 的最优区间左端点距离 $i$ 不超过 $L$ 的情况考虑过了，答案为 $f_j$ 的一个长度为 $L$ 的区间的最大值。

对于左端点的情况考虑过了，右端点也可以同样处理一个 $g_j$，答案为：

$$k_i=\max\left(\max_{i-L<j\le i}f_j,\max_{i\le j< i+L}g_j\right)$$

$f_i,g_i$ 是两个滑动窗口，而 $k_i$ 的求解也是两个滑动窗口。可以用 ST 表套单调队列或者纯单调队列轻松做到 $O(n\log n+nq)/O(nq)$。

一般情况 $O(nq+n\log^2 n)$

考虑拓展这个做法：

上述条件的核心结论是，$2L_j>R_j$，如果询问不满足这个性质怎么办？

把这个结论写成一个必要的形式，即存在 $t$ 满足 $2^t\le L\le R< 2^{t+1}$。即可满足上面的性质。

不满足？还是预处理，倍增分块，对于散块预处理需要的询问，合法区间长度在 $[2^k,2^{k+1})$，满足上面需要的性质。需要预处理 $\log$ 次，然后同理预处理出 $G_{i,j,k}$，复杂度为 $O(n\log^2 n)$。

对于询问，整块直接套用预处理的结果，散块的两个询问一定满足 $2^t\le L\le R< 2^{t+1}$，直接用上面的做法做就行了。复杂度为 $O(nq)$。

于是，我们用另外一种方法在 $O(n\log^2 n+nq)$ 的复杂度解决了这个问题。

结语

我们用两种看似不同的做法，得出了两个十分相似的解决问题的结构，这就是 DS 的有趣之处。

关于代码编写的意见，对于滑动窗口问题，ST 表的常数要远小于单调队列，但只能在预处理好的序列上做，单调队列虽然常数大，但是确不需要预处理，编码时可以酌情考虑合适的算法。