Kazun の競プロ記録

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

AtCoder Beginner Contest 238 E問題 Range Sums

AtCoder ABC ABC238 E問題 500 pts

問題

提出解答

問題の概要

長さ $N$ の整数列 $A$ が与えられる. 次の $Q$ 個の情報 $1,2, \dots, Q$ を用いて, $A_1+\dots+A_N$ を求めることは可能か?

$l_q,r_q$ と $A_{l_q}+A_{l_q+1}+\dots+A_{r_q}$

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq Q \leq \min \left(2 \times 10^5, \frac{N(N+1)}{2} \right)$
$1 \leq l_q \leq r_q \leq N$
$p \neq q \Rightarrow (l_p, r_p) \neq (l_q, r_q)$

解法

$B$ を $A$ の累積和とする. つまり, $\displaystyle B_i=\sum_{j=1}^i A_i$ とする. このとき, $A_{l_q}+\dots+A_{r_q}=B_{r_q}-B_{l_q-1}$ である.

よって, 問題は $B_{r_1}-B_{l_1-1}, \dots, B_{r_Q}-B_{l_Q-1}$ と $B_0=0$ の情報から $B_N$ が特定できるか? ということになる.

ここで, $x-y$ と $y$ の値から $x$ が特定でき, 逆に $x-y$ と $x$ の値から $y$ の値が特定できる.

従って, この問題は次の問題に帰着される.

無向グラフ $G=(V,E)$ が与えられる. $V=\{0,1,2,\dots,N \}$ で, $E=\{(l_q-1, r_q) \mid q=1,2, \dots, Q \}$ である. 頂点 $0$ と頂点 $N$ は連結か?

この問題は幅 (深さ) 優先探索や Union-Find を利用することにより, それぞれ計算量 $O(N+Q), O(N+Q \alpha(N))$ で解くことができる.