AtCoder Beginner Contest 250 E問題 Prefix Equality

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$A=(a_1, \dots, a_N), B=(b_1, \dots, b_N)$ とする. 次の $Q$ 個の質問 $1,2, \dots, Q$ に答えよ.

質問 $q$ : $\{a_1, \dots, a_{x_q} \}=\{b_1, \dots, b_{y_q} \}$ か?

制約

$1 \leq N,Q \leq 2 \times 10^5$
$1 \leq a_q, b_q \leq 10^9$
$1 \leq x_q, y_q \leq N$

解法

$F_x=\{a_1, \dots, a_{x_q} \}, G_y=\{b_1, \dots, b_{y_q} \}$ する.

次のようにして定義された列 $T^{(x)}=\left(T^{(x)}_i \right)_{i=1}^N, U^{(x)}=\left(U^{(x)}_i \right)_{i=1}^N$ を用いて, $F_x=G_y$ かどうかを判定できる.

の定義
- $i=1,2, \dots, N$ に対して, $T^{(0)}_i=0$
- のとき,
  - $b_i \in F_x$ かつ, $1 \leq j \leq y$ に対して, 「 $b_i=b_j$ ならば, $i \leq j$ 」が成り立つとき, $T^{(x)}_i =1$ , それ以外は $T^{(x)}_i=0$ .
の定義
- $i=1,2, \dots, N$ に対して, $U^{(0)}_i=1$
- のとき,
  - $b_i \in F_x$ ならば, $U^{(x)}_i=0$ , $b_i \not \in F_x$ ならば, $U^{(x)}_i=1$ .

このとき,

$\displaystyle F_x \subset G_y \iff \sum_{i=1}^y T^{(x)}_i=|F_x|$
$\displaystyle F_x \supset G_y \iff \sum_{i=1}^y U^{(x)}_i=0$

である.

ここで, $T^{(x)}$ と $T^{(x+1)}$ の関係性について,

$a_{x+1} \in F_x$ . つまり, $F_x=F_{x+1}$ ならば, $T^{(x+1)}=T^{(x)}$ である.
$a_{x+1} \not \in F_x$ であり, $b_j=a_{x+1}$ となる $j$ が存在するとき, このような $j$ のうち最小の整数を $j'$ として,

$T^{(x+1)}_i=\begin{cases} T^{(x)}_i & (i \neq j') \\ 1 & (i=j') \end{cases}$

である.

同様に, $U^{(x)}$ と $U^{(x+1)}$ の関係性について,

$a_{x+1} \in F_x$ . つまり, $F_x=F_{x+1}$ ならば, $U^{(x+1)}=U^{(x)}$ である.
$a_{x+1} \not \in F_x$ であるとき, $b_j=a_{x+1}$ となる全ての $j$ の集合を $H$ としたとき,

$U^{(x+1)}_i=\begin{cases} U^{(x)}_i & (i \not \in H) \\ 0 & (i \in H) \end{cases}$

である.

よって, 各クエリに対して, 加法に関する1点更新と区間和の処理が必要なので, BIT によって高速処理できる. クエリ先読みにより, $x$ の昇順毎に $T^{(x)}, U^{(x)}$ を更新することにしていくと, 1点更新は各要素高々1回なので, $Q$ 個の質問を全て合わせて $O((Q+N) \log N)$ で処理できる,