You are given two sequences of integers of length $N$: $A = (A_1, A_2, \ldots, A_N)$ and $B = (B_1, B_2, \ldots, B_N)$. Print the number of pairs of integers $(l, r)$ that satisfy $1 \leq l \leq r \leq N$ and the following condition.Problem Statement
Constraints
Input
The input is given from Standard Input in the following format:
$N$ $S$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$
Output
Print the answer.
Sample Input 1
4 15 9 2 6 5 3 5 8 9
Sample Output 1
6
The following six pairs of integers $(l, r)$ satisfy $1 \leq l \leq r \leq N$ and the condition in the problem statement: $(1, 1)$, $(1, 2)$, $(2, 2)$, $(2, 3)$, $(3, 3)$, and $(4, 4)$.
Sample Input 2
15 100 39 9 36 94 40 26 12 26 28 66 73 85 62 5 20 0 0 7 7 0 5 5 0 7 9 9 4 2 5 2
Sample Output 2
119
两个东西加起来要小于等于 \(S\)，太烦了。考虑固定一个，弄另一个。
和这个东西几乎没有办法固定，那只能固定最小值了。
设区间 \([l,r]\) 的最小值为 \(x\)，位置在 \(k\)。区间的最小值和位置可以用ST表求得
那么总所周知，所有跨过 \(k\) 的区间的最小值都是 \(x\)。设 \(B\) 的前缀和为 \(s\)，那么此时要让 \(s_r-s_{l-1}+x\le S\)，并满足 \(l\le k,r>k\)。要数满足要求的 \([l,r]\) 的个数。求得跨越 \(k\) 的区间数量后，递归到 \([l,k-1]\) 和 \([k+1,r]\) 数数即可。
但是这个很难弄，至少几个变量很难 \(O(1)\) 的数出来。但是我们完全可以 \(O(\min(k-l,r-k))\) 的数出来。也就是只遍历分治出来的两个区间中的小区间。这样子的复杂度就可以达到 \(O(nlogn)\)。方法时在较小的那个区间枚举 \(l/r\)，然后可以用二分求出有多少个区间符合要求。以枚举 \(l\) 为例，\(l\) 确定之后， \(s_{l-1}\) 和 \(x\) 确定，要求有多少个区间满足 \(s_r\le S-x+s_{l-1}\)，直接 lower_bound 就行了。
最终复杂度二分加只遍历小区间的 \(logn\)，最终 \(O(nlog^2n)\).
标签：integers,Min,Sum,Sample,leq,区间,ABC283Ex,ldots,10 From： https://www.cnblogs.com/mekoszc/p/17022822.html