CodeChef - ForbiddenSum

• 問題
• AC (fractional cascading)
• AC (永続セグメント木)

まずは与えられた列$A_1, ..., A_N$のForbiddenSumを求めるうまい方法を考える必要があるが、この時点でわからなかった。Editorialより。

• 列$(S_i)$を$S_0 = 0, S_{i+1} = \sum_{A_i \le S_i+1}A_i$で構成する。$S_{i+1} = S_i$が成り立ったら$S_i + 1$がForbiddenSumである。

理由を考える。簡単のために$A_1 \le ... \le A_N$としておくと、$S_i$は$(A_i)$のprefix sumとして表せるので、右端を$r_i$で表して$S_i = A_1 + ... + A_{r_i}$としておく。次のことを示せればよい:

• $A_1, ..., A_{r_i}$のsubset sumによって常に$S_i$以下のすべての非負整数が作れる。$S_i + 1$は作れない。

帰納法で示す。$i=0$の場合は明らか。$i-1$について成り立つとする。このとき、$\{A_{r_{i-1} + 1}, ..., A_{r_i}\}$のすべてのsubset sumを昇順に並べると、隣り合う要素の差は$S_i$の定義より$S_{i-1}+1$以下である。また、帰納法の仮定より$\{A_1, ..., A_{r_{i-1}}\}$のsubset sumによって$S_{i-1}$以下のすべての非負整数が作れて$S_{i-1}+1$は作れない。したがって、前半と後半の集合を合わせると、$(A_{r_{i-1} + 1}+ ...+ A_{r_i}) + S_{i-1} = (A_{r_{i-1} + 1}+ ...+ A_{r_i}) + (A_1 + ... + A_{r_{i-1}}) = S_i$以下のすべての非負整数が作れて$S_i +1$は作れないことがわかる。

また、$S_{i-1}$から$S_i$を求めるとき、増えるなら常に$S_{i-2}$以上増える（$S_{i-2}$より小さい数は$S_{i-1}$の時点で加算されているため）ので、フィボナッチ数以上のオーダーで増加する。したがって、$(S_i)$は${O}(\log \sum A_i)$で停止することになる。

与えられた区間に対して列$(S_i)$を構成することは、区間$[L_i, R_i]$について$A_{L_i}, ..., A_{R_i}$のうちの閾値以下の数の総和を求める計算を繰り返すことに相当し、これらは二次元のrange sum queryとみなせる。例えばfractional cascading付きの領域木なら${O}(\log N)$で処理できるので、クエリあたり${O}(\log N \log \sum A_i)$となる。永続セグメント木でも同じことができる。