ABC366简要题解

C

直接维护一个桶，表示每个元素当前的出现次数。
再利用这个桶直接维护答案即可。

D

三维前缀和模板题。

E

注意到答案中只会出现 \(O(n)\) 个不同 \(x\)，以及 \(O(n)\) 个不同的 \(y\)。

于是单独考虑 \(x\) 和 \(y\)，最后尺取求一下答案即可。

F

首先我第一个尝试的思路是贪心，但是很显然没法贪。

如果没法贪心，看起来就只能是 \(\text{DP}\) 了。

但是直接线性 \(\text{DP}\) 也没法做，因为你选择一些数对的顺序影响着你的答案。

于是我们希望能有一个合理的顺序——考虑排序。
注意到一个经典的思路就是，我们对于一种最终选择的顺序方案，调换其中相邻的两个数不会对其前面和后面的贡献产生影响，只会对这两个位置的值产生影响。于是我们比较优先级的时候就按照这两个数谁在前面更优来决定。
同时既然我们要拿来排序，就必须要证明出大小关系的传递性。这是我们最初的 \(\text{Cmp}\) 函数判定式：

移项，两边同除以 \(B_iB_j\) 得：

容易发现，现在的式子只与 \(i\) 本身有关，具有传递性。