Kazun の競プロ記録

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

AtCoder Beginner Contest 278 C問題 FF

AtCoder ABC278 ABC C問題 300 pts

問題

提出解答

問題の概要

SNS Twidai には $N$ 人のユーザーがおり, ユーザー $1, \cdots,$ ユーザー $N$ と名付けられている. 最初, どのユーザーも他のユーザーをフォローしていない.

次の $Q$ 個の履歴及び質問に答えよ.

$T_q=1$ : ユーザー $A_q$ がユーザー $B_q$ をフォローする. ただし, 既にフォローしている場合は何も起こらない.
$T_q=2$ : ユーザー $A_q$ がユーザー $B_q$ のフォローを解除する. ただし, 既にフォローしていない場合は何も起こらない.
$T_q=3$ : ユーザー $A_q$ とユーザー $B_q$ が互いにフォローしあっているか? 答えよ.

制約

$2 \leq N \leq 10^9$
$1 \leq Q \leq 2 \times 10^5$
$T_q=1,2,3$
$1 \leq A_q, B_q \leq N$
$A_q \neq B_q$
$T_q=3$ となる $q$ が存在する.

解法

$N$ が非常に小さい場合は $X_{a,b}$ でユーザー $a$ がユーザー $b$ をフォローしているかどうかを表している整数を用意することで処理できる. ただし, これは計算量として $O(N^2)$ 時間を要してしまう.

$N$ 個の集合 $S_1, \dots, S_N$ を用意し, 次のようにして処理できる. これらは最初空集合である.

$T_q=1$ : $S_{A_q}$ に $B_q$ を加える.
$T_q=2$ : $S_{A_q}$ から $B_q$ を削除する.
$T_q=3$ : $B_q \in S_{A_q}$ かつ $A_q \in S_{B_q}$ かどうかを判定する.

集合によって各クエリを $O(1)$ や $O(\log Q)$ 時間で処理できる. ただし, $N$ が非常に大きいので, 全てを用意することはできない. そこで, map (C++) や defaultdict (Python) を利用し, 必要になった瞬間に空集合を用意することによって, 多くても $2Q$ 個の集合を用意することで済む.

このような工夫によって $O(Q)$ 時間や $O(Q \log Q)$ 時間で処理できる.