Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 231 F 問題 Jealous Two

AtCoder ABC ABC231 F問題 500 pts

問題

提出解答

問題の概要

長さが $N$ の2つの列 $A=(A_i), B=(B_i)$ が与えられる. 以下を満たす整数の組 $(i,j)$ はいくつか?

$1 \leq i,j \leq N$
$A_i \geq A_j$ かつ $B_i \leq B_j$

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq A_i, B_i \leq 10^9$
入力はすべて整数

解法

まず, $A_i \geq A_j$ かつ $B_i \leq B_j$ という条件については順序だけを見ていることから, 座標圧縮を行うことで, $1 \leq A_i, B_i \leq N$ としてもよい. そして, $\chi(a,b)$ を $A_i=a, B_i=b$ となる $i$ の個数とすることにより, $(A_1,B_1), \dots, (A_N, B_N)$ は異なる $M$ 個の項からなるとしてもよい. 以下, $\chi(A_i, B_i)$ の情報を残し, $(A_1,B_1), \dots, (A_M, B_M)$ は互いに異なるとして良い.

$1,2, \dots, M$ の並び替え $i_1, \dots, i_M$ を以下を満たすように並び替える.

に対して, ならば, 以下のうちのどちらか一方が成り立つ.
- $A_{i_p} \lt A_{i_q}$
- $A_{i_p}=A_{i_q}$ かつ $B_{i_p} \geq B_{i_q}$

そして, 以下のように実行すると正解 $X$ を求めることができる.

$T$ を全ての項が $0$ である長さ $N$ の列とする.
$X \gets 0$
の順に以下を実行する.
- $T_{B_r}$ に $\chi(A_r,B_r)$ を加算する.
- $X$ に $\displaystyle \sum_{k=B_r}^N T_k$ を加算する.
$X$ を出力する.

$\displaystyle \sum_{k=B_r}^N T_k$ を求めるパートがボトルネックになる. ここで, $T$ にはある $1$ 点に加算することと区間和を求めることを要求する. これを得意とするデータ構造は BIT や平行二分木がある.

このようなデータ構造を用いることで, 計算量 $O(N \log N)$ で求めることができる.