Kazun の競プロ記録

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

AtCoder Beginner Contest 242 G問題 Range Pairing Query

AtCoder ABC ABC242 G問題 600 pts

問題

提出解答

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ が与えられる. 次の $Q$ 個の問 $q=1,2, \dots, Q$ に答えよ.

以下を満たす最大のを求めよ.
- $l_q \leq i_k, j_k \leq r_q \quad (k=1,2, \dots, t)$
- $2t$ 個の整数 $i_1, j_1, \dots, i_t, j_t$ は互いに異なる.
- $A_{i_1}=A_{j_1}, \dots, A_{i_t}=A_{j_t}$

制約

$1 \leq N \leq 10^5$
$1 \leq A_i \leq N$
$1 \leq Q \leq 10^6$
$1 \leq l_q \leq r_q \leq N$

解法

まず, $l,r$ が与えられたときの答え $\alpha(l,r)$ を考える. $\chi(a,l,r)$ で $A_l, \dots, A_r$ にある $a$ の数とする. すると,

$\displaystyle \alpha(l,r)=\sum_{a=1}^N \left \lfloor \dfrac{\chi(a,l,r)}{2} \right \rfloor$

となることがわかる.

ここで, $\alpha(l,r)$ がわかっているとき, $\alpha(l,r+1)$ はシグマの $a=A_{r+1}$ の部分のみ足すべき項が変わりうることを頭に入れると,

$\alpha(l,r+1)=\begin{cases} \alpha(l,r) & (\chi(A_{r+1}, l, r): {\rm even}) \\ \alpha(l,r)+1 & (\chi(A_{r+1}, l,r): {\rm odd}) \end{cases}$

となる.

これ以外にも, $\alpha(l,r)$ から $\alpha(l \pm 1, r), \alpha(l, r \pm 1)$ が比較的簡単にわかる.

このように, $\alpha(l,r)$ から $\alpha(l \pm 1, r), \alpha(l, r \pm 1)$ が比較的簡単にわかり, 求めるべき区間がたくさんある場合は Mo アルゴリズムが有効的である.

Mo アルゴリズムを簡単に説明すると, $\alpha(1,6)$ がわかっている状況から $\alpha(3,5)$ を求めたい. このとき,

$\alpha(1,6) \to \alpha(2,6) \to \alpha(3,6) \to \alpha(3,5)$

のようにして大量のクエリを処理するが, この途中経路を工夫する. このアルゴリズムを Mo アルゴリズムという.

計算量についての詳細は省略するが, $O(N \sqrt{Q})$ で求めることができる.

ei1333.hateblo.jp