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
标签:AtCoder,数字,大根堆,306,leq,补题,集合,10 From: https://www.cnblogs.com/tonyhgf/p/17496783.html