Here, we call an integer pair \((l, r)\) satisfying \(1 \leq l \leq r \leq N\) such that, as mentioned in the problem, \(\min \lbrace A_l, A_{l+1}, \ldots, A_r\rbrace + (B_l + B_{l+1} + \cdots + B_r) \leq S\), a good pair.

Consider solving a problem against segment \([L, R]\) for some integers \(L\) and \(R\) (that is, counting good pairs \((l, r)\) contained in the segment \([L, R]\)) with divide-and-conquer. Specifically, it is sufficient to count good pairs \((l, r)\) in \([L, R]\) such that \(l \leq M \leq r\) for some integer \(M\), and inspect segments \([L, M-1]\) and \([M+1, R]\) to solve the answer to the original segment recursively.

So how can we “count good pairs \((l, r)\) in \([L, R]\) such that \(l \leq M \leq r\)?” Here we introduce two approaches taking different \(M\).

[1] Letting \(M\) be the midpoint of the segment

In other words, we let \(M \coloneqq \lfloor (L+R) / 2 \rfloor\). Also, Let \(\alpha_{\mathrm{L}}\) be the cumulative \(\min\) array from \(M\) to \(L\) of \(A\), and \(\alpha_{\mathrm{R}}\) be one from \(M\) to \(R\). For convenience, let \(\alpha_{\mathrm{L}}[L-1] = \alpha_{\mathrm{R}}[R+1] = -\infty\).

One can count the number of good pairs \((l, r)\) in segment \([L, R]\) such that \(l \leq M \leq r\) by, starting from \(p = M\) and \(q = M\), repeating the following operations until it becomes “\(L \lt p\) or \(q \lt R\).”

• If \(\alpha_{L}[p-1] \geq \alpha_{\mathrm{R}}[q+1]\),

  • First, let \(p \leftarrow p-1\).
  • Then, count good pairs \((l, r)\) such that \(l = p\) and \(M \leq r \leq q\).

• Otherwise,

  • First, let \(q \leftarrow q+1\).
  • Then, count good pairs \((l, r)\) such that \(p \leq l \leq M\) and \((l, r)\).

How can we “count good pairs \((l, r)\) such that \(l = p\) and \(M \leq r \leq q\)” in the step above? At this point, for all integer pairs \((l, r)\) such that \(l = p\) and \(M \leq r \leq q\), \(\min \lbrace A_l, A_{l+1}, \ldots, A_r\rbrace\) is fixed to \(\alpha_{\mathrm{L}}[p]\). Therefore, when \(l = p\) is fixed, the range of \(r\) such that \((l, r)\) is a good pair can be found by performing binary search on the cumulative sum array of \(B\). Same applies to “counting good pairs \((l, r)\) such that \(p \leq l \leq M\) and \((l, r)\).”

As we take \(M\) at the center every time we divide the problem, the overall time complexity of this algorithm is \(O(N (\log N)^2)\).

[2] Letting \(M\) be the index that \(A\) is minimum within the segment

We take \(M\) such that \(A_M = \min\lbrace A_L, A_{l+1}, \ldots, A_R \rbrace\), and count good pairs \((l, r)\) in the segment \([L, R]\) such that \(l \leq M \leq r\).

By the choice of \(M\), for all integer pairs \((l, r)\) contained in the segment \([L, R]\), \(\min \lbrace A_l, A_{l+1}, \ldots, A_r\rbrace\) is fixed to \(A_M\). Therefore, when one of \(l\) and \(r\) is fixed, the range of the other variable such that \((l, r)\) is a good pair can be found by performing binary search on the cumulative sum array on \(B\).

So, we count good pairs with fixed \(l\) if \([L, M]\) is the shorter, and count the pairs with fixed \(r\) if \([M, R]\) is the shorter.

As we are fixing the integer contained in the shorter of \([L, M]\) and \([M, R]\) always, each integer between \(1\) and \(N\) is fixed as \(l\) and \(r\) \(O(\log N)\) times throughout the algorithm, and the total time complexity of this algorithm is \(O(N (\log N)^2)\).