合适数对

给定一个长度为 $n$ 的整数数列 $a_{1},a_{2}, \dots ,a_{n}$ 和一个整数 $t$。

请你判断共有多少个数对 $\left( {l,r} \right)$ 同时满足：

• $1 \leq l \leq r \leq n$
• $a_{l}+a_{l+1}+ \dots +a_{r?1}+a_{r} < t$

输入格式

第一行包含两个整数 $n$ 和 $t$。

第二行包含 $n$ 个整数 $a_{1},a_{2}, \dots ,a_{n}$。

输出格式

一个整数，表示满足条件的数对的数量。

数据范围

前三个测试点满足 $1 \leq n \leq 5$。
所有测试点满足 $1 \leq n \leq 2 \times {10}^{5}$，$\left| t \right| \leq 2 \times {10}^{14}$，$\left| a_{i} \right| \leq {10}^{9}。

输入样例1：

5 4
5 -1 3 4 -1

输出样例1：

5

输入样例2：

3 0
-1 2 -3

输出样例2：

4

输入样例3：

4 -1
-2 1 -2 3

输出样例3：

3

解题思路

　　设前缀和$s_{i}$表示$a_{1} + \cdots + a_{i}$，我们枚举右端点$i$和左端点$j$，来找到有多少个区间满足$s_{i} - s_{j-1} < t$。也就是$i$确定后，求前面有多少个$s_{j-1}$满足这个不等式。

　　由于我们是枚举$i$，当枚举到$i$的时候$s_{i}$已经是一个定值了，而$s_{j-1}$是要求的变量，因此$s_{j-1}$应该满足$s_{j-1} > s_{i} - t$。这就相当于问我们在$i$的前面有多少个前缀和满足大于$s_{i} - t$的。其中$j$的取值范围为$1 \leq j \leq i$，因此有$0 \leq j-1 \leq i-1$，也就是问在$0 \leq j' \leq i-1$这个区间内，有多少个$s_{j’}$满足$s_{j'} > s_{i} - t$。

　　因此每次枚举，我们要维护前面$i$个数一个有序序列，枚举完$i$后，把$s_{i}$放入这个有序序列。下次要找有多少个大于$s_{i} - t$的数时，就可以通过二分找到大于$s_{i} - t$的第一个数，那么之后的数都是满足大于$s_{i} - t$的，可以直接求得有多少个数满足这条件。

　　其中在这个题中$a_{i}$是可以小于$0$的，如果$a_{i}$都满足$a_{i} \geq 0$，那么可以用双指针做。由于$a_{i} \geq 0$，因此前缀和数组是单调递增的，根据$s_{j-1} > s_{i} - t$，可以发现当$i$增大往后移动，$s_{i} - t$会变大，因此$s_{j-1}$也应该变大，即$j$也要往后移动。因此两个指针的移动都是单调的。

　　满足这个条件的代码如下：

#include 
#include 
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL s[N];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int val;
        scanf("%d", &val);
        s[i] = s[i - 1] + val;
    }
    
    LL ret = 0;
    for (int i = 1, j = 0; i <= n; i++) {
        while (s[j] <= s[i] - m && j < i) {
            j++;
        }
        ret += i - j;
    }
    
    printf("%lld", ret);
    
    return 0;
}

　　对于这道题目，由于$a_{i}$是可以小于$0$的，因此前缀和数组不满足单调性，就不可以用上面的方法了。因为维护有序序列，因此可以用平衡树，但目前我只学过用std::set实现的平衡树，这个可以维护有序序列，但不能够知道某个数在这个有序序列的具体下标，这样就不能够知道这个数后面有几个数了。

　　这里用另外一种方法，树状数组加离散化。

　　树状数组的作用是，当枚举到$i$，我们通过树状数组来求大于$s_{i} - t$的数的个数，具体方法就是先通过树状数组来求得有多少个数在$1 \sim s_{i} - t$这个范围内，然后用$i$减去这个值就得到大于$s_{i} - t$的数的个数了。然后枚举完$i$后，$s_{i}$这个数出现次数加$1$，通过树状数组来维护动态前缀和。

　　要离散化是因为$a_{i}$的取值非常大，因此我们需要进行离散化。我们用到的数有每一个$s_{i}$以及$s_{i} - t$。还有$0$，因为一开始枚举$i=1$的时候$j-1$的取值为$0 \sim 0$，因此会用到$s_{0}$，即$0$。通过离散化后，最终需要用到的值的数量不超过$2 \times N$。

　　AC代码如下：

 1 #include 
 2 #include 
 3 using namespace std;
 4 
 5 typedef long long LL;
 6 
 7 const int N = 4e5 + 10;
 8 
 9 LL s[N], xs[N], cnt;
10 int tr[N];
11 
12 int find(LL x) {
13     int left = 1, right = cnt;
14     while (left < right) {
15         int mid = left + right >> 1;
16         if (xs[mid] >= x) right = mid;
17         else left = mid + 1;
18     }
19     
20     return left;
21 }
22 
23 int lowbit(int x) {
24     return x & -x;
25 }
26 
27 void add(int x, int val) {
28     for (int i = x; i <= cnt; i += lowbit(i)) {
29         tr[i] += val;
30     }
31 }
32 
33 int query(int x) {
34     int ret = 0;
35     for (int i = x; i; i -= lowbit(i)) {
36         ret += tr[i];
37     }
38     
39     return ret;
40 }
41 
42 int main() {
43     int n;
44     LL m;
45     scanf("%d %lld", &n, &m);
46     for (int i = 1; i <= n; i++) {
47         int val;
48         scanf("%d", &val);
49         s[i] = s[i - 1] + val;
50         xs[++cnt] = s[i], xs[++cnt] = s[i] - m; // 用到s[i]和s[i]-m
51     }
52     
53     xs[++cnt] = 0;  // 0也会被用到，因此需要加到离散化数组中
54     sort(xs + 1, xs + cnt + 1);
55     cnt = unique(xs + 1, xs + cnt + 1) - xs - 1;
56     
57     LL ret = 0;
58     add(find(0), 1);    // 一开始有0
59     for (int i = 1; i <= n; i++) {
60         ret += i - query(find(s[i] - m));   // 大于s[i]-m的数就是已有的数减去小于等于s[i]-m的数的个数
61         add(find(s[i]), 1); // s[i]出现过，因此s[i]出现次数加1
62     }
63     
64     printf("%lld", ret);
65     
66     return 0;
67 }

参考资料

　　AcWing 4316. 合适数对（AcWing杯 - 周赛）：https://www.acwing.com/video/3739/