この問題は累積和と二分探索を用いて解くことができます。

予め累積和 \(S_0=0,\ S_i=A_0+\ldots+A_{i-1}\) を計算しておきます。これにより、\(A\) の任意の区間和を \(S_R-S_L=A_L+A_{L+1}+\ldots+A_{R-1}\) により \(O(1)\) で求めることができます。

累積和を用いて与えられた条件は以下のように書き換えられます：

• \(S_y-S_x=P\)
• \(S_z-S_y=Q\)
• \(S_w-S_z=R\)

任意の \(i\) で \(A_i>0\) であることから \(S_i\) は単調増加なので、\(x\) を固定したとき \(S_y-S_x=P\) を満たす \(y\)、すなわち \(S_y=S_x+P\) となる \(y\) は二分探索により \(O(\log N)\) で求めることができます。同様に \(z,w\) も二分探索により求めることができるので、\(x\) を固定するごとに \(O(\log N)\) で条件をチェックすることができます。したがって、\(x\) を全探索することで、\(O(N\log N)\) でこの問題を解くことができます。

なお、実装上は \(S\) をsetで保持することで、明示的に二分探索を行う必要がなくなります。

実装例(C++)