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

对于行（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;

}

图片来自OIWIKI 

扫描线算法就是用线段树给每个矩形的上下边进行标记，下面标记为 $1$，上面标记为 $-1$，然后从下往上不断统计答案，然后更新线段树。 

需要注意的是，每个线我们保存的是一个区间的信息，所以需要注意 $r + 1$ 或 $r - 1$。 

因为每个节点坐标的取值区间太大，所以我们要离散化，然后二分找值。

定义 $f(u,k)$ 表示以 $u$ 为根的子树里有 $k$ 个节点与 $u$ 联通的最小道路，$size(u)$ 为 $u$ 的子树内节点个数。

初始状态：$\forall u \in [1,n],f(u,1)=|son_u|$，其中 $|son_u|$ 表示 $u$ 的出边个数。

转移方程：

$$\sum\limits_{v\in son_u,j\in [1,size(u)],k\in [1,size(v)]} f(u,j+k)=\min\{f(u,j)+f(v,k)-2\}$$

其中 $-2$ 是因为最初 $u,v$ 两点的连边被断开，多加的 $2$ 要在这里减回来。

感性理解一下为什么说时间复杂度是 $\Theta(n^2)$ 的：

发现主要的时间复杂度是在 $j,k$ 的枚举上，而 $j,k$ 的枚举其实等价于枚举点对。

原因不难理解，每两个节点只有在它们的 LCA 处会被枚举到。

因此，总的时间复杂度是 $\Theta(n^2)$