以下では、\(1 \leq l \leq r \leq N\) を満たす整数の組 \((l, r)\) であって問題文中の条件 \(\min \lbrace A_l, A_{l+1}, \ldots, A_r\rbrace + (B_l + B_{l+1} + \cdots + B_r) \leq S\) を満たすものを良い組と呼びます。

整数 \(L, R\) に対して、区間 \([L, R]\) に関する問題（すなわち、区間 \([L, R]\) に含まれる良い組 \((l, r)\) を数える問題）を、分割統治法によって解くことを考えます。 具体的には、\(L \leq M \leq R\) を満たす整数 \(M\) をとり、 \([L, R]\) に含まれる良い組 \((l, r)\) のうち \(l \leq M \leq r\) を満たすもののみを数え、残りの部分は区間 \([L, M-1]\) に関する問題と区間 \([M+1, R]\) に関する問題に帰着して再帰的に解きます。

そのためには「 \([L, R]\) に含まれる良い組 \((l, r)\) のうち \(l \leq M \leq r\) を満たすもののみを数える」部分が解ければ良いです。 以下では、\(M\) の取り方が異なる \(2\) つの解法を紹介します。

[1] 区間の中央を \(M\) とする解法

つまり、\(M \coloneqq \lfloor (L+R) / 2 \rfloor\) とします。 また、\(A\) の \(M\) から \(L\) の方向への累積 \(\min\) 配列を \(\alpha_{\mathrm{L}}\) 、\(A\) の \(M\) から \(R\) の方向への累積 \(\min\) 配列を \(\alpha_{\mathrm{R}}\) とします。 便宜上、\(\alpha_{\mathrm{L}}[L-1] = \alpha_{\mathrm{R}}[R+1] = -\infty\) とみなします。

区間 \([L, R]\) に含まれる良い組 \((l, r)\) のうち \(l \leq M \leq r\) を満たすものを数えるには、\(p = M, q = M\) の状態から始め「 \(L \lt p\) または \(q \lt R\) 」である限り、下記の手順を繰り返せば良いです。

• \(\alpha_{L}[p-1] \geq \alpha_{\mathrm{R}}[q+1]\) のとき、

  • まず、\(p \leftarrow p-1\) とする。
  • そして、\(l = p\) かつ \(M \leq r \leq q\) を満たす良い組 \((l, r)\) を数える。

• そうでないとき、

  • まず、\(q \leftarrow q+1\) とする。
  • そして、\(p \leq l \leq M\) かつ \(r = q\) を満たす良い組 \((l, r)\) を数える。

上の手順にある、「 \(l = p\) かつ \(M \leq r \leq q\) を満たす良い組 \((l, r)\) を数える」方法を補足します。 これを行うとき、\(l = p\) かつ \(M \leq r \leq q\) を満たすすべての整数の組 \((l, r)\) について、\(\min \lbrace A_l, A_{l+1}, \ldots, A_r\rbrace\) は \(\alpha_{\mathrm{L}}[p]\) に固定されます。 このことを用いると、\(l = p\) と固定したときに、\((l, r)\) が良い組となるために \(r\) の取り得る範囲は \(B\) の累積和配列上で二分探索を行うことで求まります。 「 \(p \leq l \leq M\) かつ \(r = q \)を満たす良い組 \((l, r)\) を数える」方法も同様です。

問題を分割する過程で \(M\) を区間の中央にとっていくことから、アルゴリズム全体の時間計算量は \(O(N (\log N)^2)\) です。

[2] 区間内で \(A\) が最小値をとる位置を \(M\) とする解法

\(A_M = \min\lbrace A_L, A_{l+1}, \ldots, A_R \rbrace\) を満たすように \(M\) を取り、区間 \([L, R]\) に含まれる良い組 \((l, r)\) のうち \(l \leq M \leq r\) を満たすものの個数を求めます。

\(M\) の選び方より、区間 \([L, R]\) に含まれ \(l \leq M \leq r\) を満たすすべての整数の組 \((l, r)\) について \(\min \lbrace A_l, A_{l+1}, \ldots, A_r\rbrace\) は \(A_M\) に固定されます。 このことを用いると、\(l\) または \(r\) の一方を固定したとき、\((l, r)\) が良い組であるために他方が取り得る範囲は \(B\) の累積和配列上で二分探索を行うことで求まります。

そこで、\([L, M]\) と \([M, R]\) のうち、\([L, M]\) の方が短い場合は \(l\) を固定する場合の、\([M, R]\) の方が短い場合は \(r\) を固定する場合のすべてについて良い組を数えます。

つねに、\([L, M]\) と \([M, R]\) の短い方に含まれる側の整数を固定することから、本問題全体を解く際に \(1\) 以上 \(N\) 以下の各整数が \(l\) または \(r\) として固定される回数はアルゴリズム全体で \(O(\log N)\) 回であり、アルゴリズム全体の時間計算量は \(O(N (\log N)^2)\) です。