十分大きな整数 \(P\) を取り，\(2^{A_i}\) の累積和 \(\mathrm{mod}\ P\) を計算しておきます．\((l,k)\) に対して \(2^{A_l}+\ldots+2^{A_r}\equiv 2^k \pmod{P}\) を満たす \(r\) が存在するかどうかを，連想配列を用いることで高速に判定できるようにしておきます．

\(2^{A_l}+\ldots+2^{A_r}\) が \(2\) べきになるとき，その値は \(M=\max(A_l,\ldots,A_r)\) としたとき \(2^M,2^{M+1},\ldots,2^{M+\lfloor\log_2 N\rfloor}\) のいずれかです．

条件を満たす \((l,r)\) の個数を分割統治で求めます．区間 \([L:R]\) に対し，\(A_m=\max(A_L,\ldots,A_R)\) を満たす \(m\) を一つとり，\(L\leq l\leq m\leq r\leq R\) を満たす \((l,r)\) のうち条件を満たすものを数えます．

\(m-L\leq R-m\) の場合，各 \(l=L,\ldots,m\) および \(k=A_m,A_m+1,\ldots,A_m+\lfloor\log_2 N\rfloor\) に対して，\(2^{A_l}+\ldots +2^{A_r}=2^k\) を満たす \(r\ (m\leq r\leq R)\) が存在するかを判定します．\(m-L\gt R-m\) の場合は \(r\) を動かして判定します．

計算量は期待 \(O(N\log^2 N)\) です．定数倍が十分に軽い \(O(N\log^3 N)\) も通るかもしれません．

---

確率評価について

\(P\) を \(2^{56}\) 以上 \(2^{63}\) 未満のランダムな素数とします．

補題. \(0\) 以上 \(2^{200018}\) 未満の整数 \(a, b\ (a\neq b)\) に対し，\(a\equiv b\ \pmod{P}\) となる確率は \(1.67\times 10^{-14}\) 程度以下である．

（証明）\(2^{56}\) 以上の素数を昇順に \(p_1,p_2,\ldots\) としたとき，\(p_1p_2\ldots p_k\gt 2^{200018}\) となる最小の \(k\) は \(k=3562\) です．素数定理より \(2^{56}\) 以上 \(2^{63}\) 未満の素数は \(2.14\times 10^{17}\) 個程度と見積もれるため，\(a\equiv b\) となる確率は \(\dfrac{3561}{2.14\times 10^{17}}\approx 1.67\times 10^{-14}\) 以下です．（証明終）

正しい答えを出力するためには，以下の条件を満たす必要があります．

• すべての \((l, r, k)\) の組 \((1 \le l \le r \le N,\ M \le k \le M + \log_2 N)\) に対して，\(2^{A_l} + 2^{A_{l+1}} + \dots + 2^{A_r} \ne 2^k\) ならば，\(2^{A_l} + 2^{A_{l+1}} + \dots + 2^{A_r} \not\equiv 2^k \pmod{P}\)

すべての \((l, r, k)\) の組がこれを満たす確率は \(1-1.67\times 10^{-14} \times \frac{N(N+1)}{2}(\lfloor\log_2 N\rfloor + 1)\) 以上であり，これは \(N=2\times 10^5\) のときおよそ \(1-6.01\times 10^{-3}\) です．

以下のような工夫をすることで，失敗する確率を減らすことができます．

1. \(64\) bit 素数を \(2\) つ用いる場合

累積和 \(\mathrm{mod}\ P\) と位置が一対一対応することを前提とする実装の場合，\(l\lt r\) ならば \(\sum_{i=1}^l 2^{A_i}\not\equiv \sum_{i=1}^r 2^{A_i}\mathrm{mod}\ P\ (☆)\) が満たされる部分がボトルネックとなり，失敗する確率は \(2\times 1.67\times 10^{-14} N(N+1)/2\approx 6.68\times 10^{-4}\) 以下です．

また，\((☆)\) を満たすまで \(P\) を乱択するようにすると，失敗する確率は \((1.67\times 10^{-14})^2 \times \frac{N(N+1)}{2}(\lfloor\log_2 N\rfloor + 1)\approx 1.00\times 10^{-16}\) 以下です．

2. \(64\) bit 素数を乱択して問題を \(5\) 回解き，出てきた答えの多数決を出力する場合

失敗確率はおよそ \(\binom{5}{3}(6.01\times 10^{-3})^3\approx2.17\times 10^{-6}\) 以下です．

3. \(128\) bit 素数を用いる場合

同様の確率評価により失敗する確率を \(10^{-22}\) 程度で抑えることができます．

なお，\(64\) bit 素数を用いた場合の理論上の確率評価は \(6.01\times 10^{-3}\) でしたが，実際にはずっと低い確率になることが予想できます．（実用上の確率評価：累積和の各要素をランダムだと仮定すると，素数 \(1\) つの場合は \(1-\dfrac{N^2\log_2 N}{P}\) 程度の確率で正しい答えを出力します．）