まずは与えられた列A1,...,ANのForbiddenSumを求めるうまい方法を考える必要があるが、この時点でわからなかった。Editorialより。
- 列(Si)をS0=0,Si+1=∑Ai≤Si+1Aiで構成する。Si+1=Siが成り立ったらSi+1がForbiddenSumである。
理由を考える。簡単のためにA1≤...≤ANとしておくと、Siは(Ai)のprefix sumとして表せるので、右端をriで表してSi=A1+...+Ariとしておく。次のことを示せればよい:
- A1,...,Ariのsubset sumによって常にSi以下のすべての非負整数が作れる。Si+1は作れない。
帰納法で示す。i=0の場合は明らか。i−1について成り立つとする。このとき、{Ari−1+1,...,Ari}のすべてのsubset sumを昇順に並べると、隣り合う要素の差はSiの定義よりSi−1+1以下である。また、帰納法の仮定より{A1,...,Ari−1}のsubset sumによってSi−1以下のすべての非負整数が作れてSi−1+1は作れない。したがって、前半と後半の集合を合わせると、(Ari−1+1+...+Ari)+Si−1=(Ari−1+1+...+Ari)+(A1+...+Ari−1)=Si以下のすべての非負整数が作れてSi+1は作れないことがわかる。
また、Si−1からSiを求めるとき、増えるなら常にSi−2以上増える(Si−2より小さい数はSi−1の時点で加算されているため)ので、フィボナッチ数以上のオーダーで増加する。したがって、(Si)はO(log∑Ai)で停止することになる。
与えられた区間に対して列(Si)を構成することは、区間[Li,Ri]についてALi,...,ARiのうちの閾値以下の数の総和を求める計算を繰り返すことに相当し、これらは二次元のrange sum queryとみなせる。例えばfractional cascading付きの領域木ならO(logN)で処理できるので、クエリあたりO(logNlog∑Ai)となる。永続セグメント木でも同じことができる。