E

题目大意

给定数字$k$，规定数组 $A$ 的函数 $f(A)$ ：$A$ 数组前 $k$ 大数字的和

• 如 $A=[1,_3,7,~4]$ ，$k=2$ ，则 $f(A)=7+4=11$

现在给定最大数组长度 $n$ ，有 $q$ 组操作，每次将第 $x$ 个数字修改为 $y$ ，输出每次操作后的 $f(A)$

其中 $0<k \leq n \leq 5\times 10^5,~q\leq 5\times 10^5, ~y\leq 10^9$

思路

考虑用一个小根堆 $X$ 和一个大根堆 $Y$，小根堆 $X$ 里放 $A$ 数组内前 $k$ 大的数字，大根堆 $Y$ 里放剩下的数字。每次修改后判断：

• 若 $A[x]$ 没被修改过，则在 $Y$ 内插入 $y$ ，并记录 $A[x] = y$
• 若 $A[x]$ 被修改过，则先在 $X$ 和 $Y$ 中删掉 $A[x]$ ，再在 $Y$ 中插入 $y$

然后执行平衡操作：判断大根堆 $Y$ 内最大的数字是否比小根堆 $X$ 内最小的数字大，如果是，交换两个数字

Code: https://atcoder.jp/contests/abc306/submissions/42763724

F

题目大意

对于两个有序集合 $A,B$ ，令有序集合 $C=A\cup B$ ，规定 $f(A,B)=\sum_{i=1}^{|A|} k_i$ ，其中 $k_i$ 是 $A[i]$ 在 $C$ 内的位置

现在给出 $n$ 个大小为 $m$ 的集合 $S_1,S_2,\cdots,S_n$ ，求 $ \sum_{1\leq i < j \leq n} f(S_i,S_j)$

其中 $n \leq 10^4,~m \leq 10^2, ~A_{i,j} \leq 10^9$ , 保证 $S_i \cap S_j = \emptyset$

思路

我的思路跟题解不太一样

现将所有数字一起排序，记为集合 $S$ 。并将每一个给定集合 $S_i$ 排序，然后考虑 $A_{i,j}$ 的贡献：

$A_{i,j}$ 的贡献是： $S$ 比它小的数字的数量 + 它在 $S_i$ 中的位置 $\times$ $S_i$ 作为 $A$ 而非 $B$ 的次数

也就是：$S$ 比它小的数字的数量 + 它在 $S_i$ 中的位置 $\times (n-i)$

为了避免重复计算，当考虑过 $A_{i,j}$ 后需要将它从集合 $S$ 中删掉。

为了在 $O(NlogN)$ 的复杂度内处理 $S$ ，考虑离散化 $A_{i,j}$ + 二叉索引树（Fenwick Tree）

Code: https://atcoder.jp/contests/abc306/submissions/42777281