T1

100%

• 方法1：

因为 $n$ 的范围不超过 $100$，可以直接三重循环枚举选哪三个人，选的人不要重复就可以了。

时间复杂度 $O(n^3)$。

• 方法2：

显然选能力值最大的三个人是最优的。如果 $n$ 的范围达到了 $10^5$，可以将能力值排序，然后取最大的三项之和。

时间复杂度 $O(n\log(n))$。

• 方法3：

可以不用排序，直接维护最大的三个值 $mx[0],mx[1],mx[2]$，可以参考以下代码：

now = a[i];
for (int j = 0; j < 3; j++) {
	if (now > mx[j])
		swap(now, mx[j]);
}

时间复杂度 $O(n)$。

T2

60%

两重循环，外层循环枚举第 $i$ 个人，内层循环枚举 $1\leq j< i$ 验证是否高度都低于 $i$。

时间复杂度 $O(n^2)$。

100%

用一个变量维护前缀最大值 $mx$，如果 $h_i> mx$ 说明 $i$ 前面的人高度都低于他，答案增加 $1$。

时间复杂度 $O(n)$。

T3

30%

直接三重循环枚举 $i,j,k$，如果满足 $A_i=A_j=A_k$ 那么答案增加 $1$。

时间复杂度 $O(n^3)$。

60%

对于测试点#4~6，统计每种数字分别出现了多少次。假设数字 $x$ 出现了 $k$ 次，那么 $A_i=A_j=A_k$ 的三元组有 $\binom {k}{3}$ 个。

因为 $-10^6\leq A_i\leq 10^6$，所以可以直接用数组来统计，加一个偏移量即可，比如 $x$ 的出现次数维护在 $num[x+1000005]$。

因为只选三个，可以直接用 $\binom {k}{3}=\frac{k\times(k-1)\times(k-2)}{1\times 2\times 3}$ 计算。

记 $A_i$ 的值域跨度为 $W=\max\{A_i\}-\min\{A_i\}$。

时间复杂度 $O(n+W)$。

结合第一部分可以拿到 $60\%$ 的分数。

100%

• 方法1：

$-10^9\leq A_i\leq 10^9$ 的数据范围下不能用数组来维护了。

可以将 $A_i$ 排序，这样相同的值的位置就在一起了，就可以统计每种数字的出现次数了。

时间复杂度 $O(n\log(n))$。

• 方法2：

也可以用 $\text{map}$ 来统计每种数字的数量。

时间复杂度 $O(n\log(n))$。

T4

20%

对于每个询问，暴力验证每个 $a_i$ 是否是 $x_i$ 的倍数。

时间复杂度 $O(qn)$。

50%

对于测试点#3~5， $n$ 和 $q$ 的范围达到了 $10^6$，但是 $a_i$ 和 $x_i$ 的范围只有 $1000$，所以可以预处理每个 $x_i$ 对应的答案。

先统计 $a$ 中每种数字出现的次数 $num[i]$，再用双重循环枚举 $i$ 和 $j$，如果 $j$ 是 $i$ 的倍数，那么 $ans[i]+=num[j]$。

记 $a_i$ 最大值为 $A=\max\{a_i\}$。

时间复杂度 $O(n+A^2+q)$。

结合第一部分可以拿到 $50\%$ 的分数。

100%

发现在第二部分中只有 $j$ 是 $i$ 的倍数时才维护答案。所以我们内层循环枚举 $j$ 时直接枚举 $i$ 的倍数。

实现上类似埃氏筛。

时间复杂度 $O(n+A\log(A)+q)$。

T5

20%

用 $\text{Floyd}$ 算法处理出任意两点间的距离，然后枚举所有 $k!$ 种访问顺序。

注意代表无法到达的无穷大要设置得足够大。

注意最后要回到点 $1$。

时间复杂度 $O(n^3+k!)$。

30%

对于测试点#3，因为 $k=1$ 所以路线只有 $1→a_1→1$ 这一条。

用 $\text{Dijkstra}$ 等单源最短路算法，分别从 $1$ 和 $a_1$ 出发，求出这两段最短路的长度再加起来。

时间复杂度 $O(m\log(m))$。

结合第一部分可以拿到 $30\%$ 的分数。

50%

对于测试点#4~5，路线有 $1→a_1→a_2→1$ 和 $1→a_2→a_1→1$ 两条。

先枚举访问顺序，分别从 $1,a_1,a_2$ 出发跑单源最短路，按顺序求出每段最短路的长度加起来。再比较两种路线哪条更短。

时间复杂度 $O(k!m\log(m))$ 。

结合第一部分可以拿到 $50\%$ 的分数。

100%

不难发现过程中用到的最短路，起点和终点全都是 $1$ 或 $a_i$，所以我们分别从这 $k+1$ 个点出发跑最短路，预处理出 $(k+1)^2$ 段最短路的长度。

然后再枚举访问顺序，计算每种路线的长度，比较出最短的一条路线。

时间复杂度 $O(km\log(m)+k!)$。

T6

10%

操作 $2$ 就是从大到小选，操作 $3$ 就是从小到大选。 $n$ 和 $q$ 的范围都是 $500$，可以直接暴力维护 $A$。

每次查询前需要排序，推荐两种实现方法：

①将 $A$ 复制到数组 $B$，对 $B$ 进行排序。

②用 $\text{pair}$ 同时存储值和下标，询问前按值排序，询问后按下标排序还原。

然后暴力枚举取多少个就可以了。

注意答案为 $0$ 或 $-1$ 的情况。

时间复杂度 $O(nq\log(n))$。

20%

对于测试点#2，因为 $A_i$ 和 $y$ 的范围只有 $50$，可以用 $num[v]$ 维护 $A$ 中有多少项值为 $v$。

操作 $1$ 只要将原本的 $num[A_x]--$，再将 $num[y]++$ 即可。

询问时直接枚举取的最后一项的值，通过前缀和的方式来计算答案。

记 $A_i$ 的最大值为 $M=\max\{A_i\}$。

时间复杂度 $O(Mq)$。

结合第一部分可以拿到 $20\%$ 的分数。

40%

对于测试点#3~4，没有修改操作的情况下，可以直接对 $A$ 进行排序。

查询时可以用二分的方法来求答案。

时间复杂度 $O((n+q)\log(n))$。

结合第一、第二部分可以拿到 $20\%$ 的分数。

80%

用权值线段树维护区间和，二分取的最后一项的值，思路类似测试点#2。

时间复杂度 $O(M+q\log^2(M))$。

100%

其实询问就对应权值线段树的前缀区间或后缀区间，可以用线段树二分的技巧，代替外层的对最后一项取值的二分。

具体来说，对于询问 $2$，对应线段树上一个后缀区间，如果当前节点的右子树的和大于等于 $v$，那么在右子树内继续寻找；否则 $v$ 减去右子树的和，在左子树内继续寻找。对于询问 $3$，就是找前缀区间，思路类似。

时间复杂度 $O(M+q\log(M))$。