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
- 306 Beginner AtCoder Contest ABCbeginner atcoder contest 306 306 beginner atcoder contest beginner atcoder contest abc atcoder beginer contest 306 atcoder abc 306 def contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335