\(A = \max_i A_i\) と書くことにします．

列のブロック分割により解くことができます．適当なブロックサイズ \(S\) をとり，列を \(N/S\) 個のブロックに分割します．

\(A_i\) に対する答の計算は次のように行えます．\(A_i\) が \(p\) 番目のブロックにあるとします．

• \(q<p\) に対して \(q\) 番目のブロックにある項からの寄与を計算する．
• \(p\) 番目のブロック内からの \(A_j\) （\(j\leq i\)）からの寄与を計算する．

後者は愚直な方法で，\(i\) ごとに \(O(S)\) 時間，全体で \(O(NS)\) 時間です． 前者はブロックごとに subset zeta 変換をすればよいです．ブロックごとに \(O(A\log A)\) 時間の計算が必要で，クエリは \(i\) ごとに \(O(1)\) 時間です．全体では \(O(N+N/S\cdot A\log A)\) 時間です．

全体では \(O(NS+NA\log A/S)\) 時間で，\(S\) を適切にとることで \(O(N\sqrt{A\log A})\) 時間となります．公式解説の方法よりすこし計算量オーダーは悪いですが，制約内の時間で解くことが可能です．なお，分割統治法を使って，\([L,M)\) から \([M,R)\) への寄与を考え，\(R-L\) の大きさに応じて計算方法を使い分けることでも実質的に同様の解法が得られます．

• (3563ms) https://atcoder.jp/contests/arc205/submissions/68596241

コンテスト終了時点での fastest は，この手法を離散対数前計算を使って高速化したものです．

• (733ms) https://atcoder.jp/contests/arc205/submissions/68595922