题目描述

给定一个长度为 $n$ 的整数数列 $a_1,a_2,…,a_n$ 和一个整数 $t$。

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

$1≤l≤r≤n$
$a_{l}+a_{l+1}+…+a_{r−1}+a_{r}<t$

前言

本题真的非常的有意思，我也是被这题绊住了，用了大约40分钟才想出正解，压哨AC……

只能说技不如人吧QAQ，但是毕竟做出来了，那就给大家写一篇题解

分析

看到静态求和，可以联想到前缀和，于是我们先求出整个序列的前缀和数组$sum$。

这时脑中顿时蹦出一个想法：枚举右端点，然后二分出第一个满足条件的左端点。

二分的判断条件：$sum_r-sum_{l-1}<t$

可惜啦，由于有负数的存在，单调性并不满足，所以二分是假做法。

那怎么办呢？

我又得到了天启：可以用一个数据结构把前面的前缀和打散放进去，而不必拘泥于原序列的限制。

每个左端点 $l$ 满足条件当且仅当：

$sum_r-sum_{l-1}<t$

即：$sum_{l-1}>sum_r-t$

正解：在值域上维护一个树状数组，维护每个前面的前缀和数值的个数的和，枚举每个右端点$r$，每次将答案累加上树状数组中大于$sum_{r}-t$的总个数，然后再给 $sum_r$ 这个位置的个数加上$1$，方便后续的计算

由于值域很大很大，树状数组开不下，所以我们要先将前缀和数组离散化

AC代码：

#include<bits/stdc++.h>
#define int long long
#define lowbit (x&-x)
using namespace std;
const int N=1000010;
int n,m;
int s[N];
int tr[N];
vector<int> nums;
void add(int x,int k){ //树状数组修改操作
    for(int i=x;i<=1000000;i+=lowbit(i)) tr[i]+=k;
}
int sum(int x){ //树状数组查询操作
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int get(int x){ //二分获取离散化之后的值
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin()+1;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int i=0;i<=n;i++){ //将所有前缀和以及后续询问用到的数值全部离散化
        nums.push_back(s[i]);
        nums.push_back(s[i]-m);
    }
    sort(nums.begin(),nums.end());  //离散化之数组排序
    nums.erase(unique(nums.begin(),nums.end()),nums.end()); //离散化之判重
    int res=0;
    add(get(s[0]),1); //将 0 这个位置的前缀和加入树状数组
    for(int i=1;i<=n;i++){
        res+=sum(1000000)-sum(get(s[i]-m)); //答案累加上树状数组中大于sum[r]-t的总个数
        add(get(s[i]),1); //给sum[r]这个位置的个数加上1，方便后续的计算
    }
    cout<<res;
    return 0;
}