ABC306 - F - Merge Sets
問題
$ \begin{aligned}f(A,B) &=\sum_{a \in A}A \cup B における a \,以下の要素の個数 \\ &= \sum_{a \in A}Aにおけるa以下の要素の個数 + \sum_{a \in A}Bにおけるa以下の要素の個数 \\ &= \frac{M(M+1)}{2}+ \sum_{a \in A}Bにおけるa以下の要素の個数\end{aligned}
$ \begin{aligned} &\quad\sum_{1 \leq i<j\leq N}f(S_i,S_j) \\ &= \sum_{1 \leq i<j\leq N}\sum_{a \in S_i}S_i \cup S_jにおけるa以下の要素の個数 \\ &=\sum_{1 \leq i<j\leq N}\left(\frac{M(M+1)}{2}+ \sum_{a \in S_i}S_jにおけるa以下の要素の個数\right)\\ &= \frac{N(N-1)}{2}\cdot\frac{M(M+1)}{2}+\sum_{1 \leq i<j\leq N}\sum_{a \in S_i}S_jにおけるa以下の要素の個数 \\ &= \frac{N(N-1)}{2}\cdot\frac{M(M+1)}{2}+ \sum _{i=1}^{N-1}\sum_{a \in S_i}S_{i+1} \cup S_{i+2}\cup\dots\cup S_Nにおけるa以下の要素の個数\end{aligned}
$ iを降順に見て、$ S_i内の要素$ aを降順に
$ seg[0, a)をansに加算
$ segのインデックス$ aに$ 1を追加
code: f.py
N, M = na()
S = []
for i in range(N):
S.append(a)
S.sort()
for i in range(N):
Aij = bisect_left(S, Aij) seg = SegTree(N * M)
ans = (N * (N - 1) * M * (M + 1)) // 4
ans += seg.fold(0, a)
seg.set_val(a, 1)
print(ans)