题解原作者：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)$

思路：

    求出每个数据包在网络中存在的最（晚）后时刻，不妨记作 $last$，则 $last>T$ 的数据包数即是答案。

要点：

    1、对于被复制的某数据包，服务器 $i$ 只会转发最早且第一次到达自己的那个复制包，因为后续到达的相同数据包将会被接收而不再转发；

    2、最早到达服务器 $i$ 的复制包一定是通过最短路（最少传输时间）抵达的，然后通过服务器 $i$ 的最长出边转发出去的复制包可能会在网络中存在更久；

    3、那么，对于服务器 $i$ 而言，某数据包传输过程分为两段：（1）从起点 $s$ 沿最短路抵达服务器 $i$；（2）沿服务器 $i$ 最长边转发至邻接服务器；

    则：某数据包传输时间 $=$ $shortest[i]$ $+$ $farest[i]$，前者是从 $s \sim i$ 的最短路，后者是 $i$ 的最长出边；

    综上，$last = max\{ shortest[i] + farest[i] \} + startime$（开始传输时刻）