（实际上是我比赛时的草稿，可能会有些跳跃，不过总体应该还算清晰）

$y$ 表示扩大后的长减去 $\Delta y$，$x$ 同理

下面是思路：

最小情况： 所有三角形的斜边作为向量相加为对角线(斜边为路线)，则三角形最小时直角顶点为 $ (x_i, y_i) $

相似 => $\displaystyle\frac{y}{\Delta x} = \frac{a_i}{b_i}, \frac{x}{\Delta y} = \frac{b_i}{a_i} $ => $ \displaystyle{ a_i \Delta x + b_i \Delta y = k }$

故 k 的最小值大于等于左式

$ \displaystyle{ a_i \times (x_i - x_{i - 1}) + b_i \times (y_i - y_{i - 1}) \leq k }$

移项，得

$ \displaystyle{ y_i \le \frac{k - a_i \times (x_i - x_{i - 1})}{b_i} + y_{i - 1} }$

观察三角形，易得（画出来的话可能会直观一点） 

$ \displaystyle{ \frac{k}{a_i} \ge \Delta x = x_i - x_{i - 1} \\ \text{于是有} \\ x_{i - 1} \ge x_i - \frac{k}{a_i} }$

又 

$ \displaystyle{ x_i - x_{i - 1} \ge 0 } $

所以 

$ \displaystyle{ x_i \ge x_{i - 1} \ge x_i - \frac{k}{a_i} } $

接下来，由得到的这两组不等式就可以求得答案了，即枚举除定值外的 $i, x_i, x_{i - 1}, k$ 

如果因变量 $y_i$ 大于等于 $m$，就满足题目要求。

具体来说，最外面枚举 $k$，然后枚举积木，横坐标，得到 $y_n$ 的最大值，然后和 $m$ 比较，找到最小的 $k$。

根据上面的描述，不难想到状态表示：$f[i, j]$ 表示枚举到第 $i$ 个积木，横坐标枚举到 $j$ 时纵坐标的最大值，最后和 $m$ 比较的是 $f[n, m]$。

最后，只是简单的枚举其实还不能通过这一题，因为我们并不知道答案的具体取值范围，如果是 $1 \times 10^9$ 的级别，枚举一万年也算不出来，因为我们是要找最小的满足条件的 $k$（大于这个值的都满足条件），所以对于 $k$，我们用二分来找到答案。

最后的时间复杂度应该是 $O(nm^2 \log r) \ (r \text{ 取你取的二分边界})$

这个题只是暴力枚举会超时，考虑优化。

对于行（y 轴），我们用双指针暴力枚举，时间复杂度是 $O(m)$ 。

对于列（x 轴），维护每一列（两个行指针间）的最值，然后用双指针枚举每一列，用单调队列维护两个列指针间的最值信息，求得矩形在 x 轴上的最长长度，然后乘以暴力枚举的 y 轴长度，时间复杂度是 $O(n)$。

最后，整体的时间复杂度是 $O(mn) \ (T(m, n) = 100mn = O(mn))$。

题解原作者：2017级吴昊钟 NOI2019铜牌

难度：普及+/提高

算法一：暴力枚举

在 $[ 0,n ]$ 的范围内暴力枚举 $m$ 的取值，直接统计 $[m,n]$ 之间的数中 $0$ 出现的次数为 $k$ 的最大 $m$ 的值。

时间复杂度：$O(N^2)$

期望得分：$30$分

算法二：前缀和+扫描法

在 $[0,n]$ 的范围内扫描，每一次进位使用类似高精度加法的方式维护 $0$ 出现的次数的变化情况，选取 $sum(n)-sum(m-1)$ 的值为 $k$ 的最大 $m$ 的值。

时间复杂度：$O(N)$

期望得分：$50$分

算法三：前缀和+组合计数

利用加法原理和乘法原理可以直接计算出 $f(n)$ 为 $[0,n]$ 之间的数中 $0$ 出现的次数，从 $n$ 开始倒序扫描选取第一个 $sum(n)-sum(m-1)$ 的值为 $k$ 的 $m$ 即可。也可以将算法二倒序维护解决。

时间复杂度：$O(N-M)$

期望得分：$70$分

算法四：二分法+前缀和+组合计数

在前一个算法的基础上利用二分法快速索引满足条件的 $m$ 的最大值即可。

时间复杂度：$O(log_{2}N)$

期望得分：$100$分

std 似乎是直接插排，但我并不会这种做法，讲一下我的想法。

首先，想一想就可以发现，$a_i$ 插排后的位置即为原序列中 $\lt a_i$ 的数的数量加上前 $i$ 个数中等于 $a_i$ 的数量。

发现这题的修改数量和 $n$ 的范围都非常小，不难想到标算是 $\mathcal{O}(n^2)$ 级的。

那么可以设计出以下算法：

首先设 $cnt_x$ 为 $a_x$ 插排后在原序列中的位置。

根据上述算法 $\mathcal{O}(n^2)$ 算出 $cnt$ 数组，然后进入询问。

对于修改操作，直接暴力地除去原 $a_x$ 的贡献，计算 $v$ 的贡献，并把 $cnt_x$ 再求出来。

对于询问操作，直接输出 $cnt$ 即可。

时间复杂度 $\mathcal{O}(n^2 + 5 \times 10^3 \times n)$，常数有点大，洛谷和 CCF 的评测机应该是能卡过去，但 COGS 需要一点常数优化，而且要手动吸氧（开O2）

#include<cstdio>

#include<iostream>

using namespace std;

int main(){

int a, b;//定义两个加数

freopen("aplusb.in", "r", stdin);//导入文件

freopen("aplusb.out", "w", stdout);

cin >> a >> b;//输入加数

cout << a+b;//相加并输出

fclose(stdin);//关闭文件

fclose(stdout);

return 0;

}