题目链接

麻了，这种题好抽象啊…不是很会…

分析：

由于求区间和，所以首先我们做一下前缀和。
我们从前往后枚举，把当前的i看作是区间右端点r；
那么问题就转换成，在r前面有多少的l，满足sum[r] - sum[l-1] < t;
变换一下式子：sum[r] - t < sum[l-1];
问题就转换成，有多少个l，满足sum[r] - t < sum[l-1];

由于sum[r] - t这个每次都是知道的，关键是sum[l-1]；
我们可以利用桶的思想，搞一个坐标轴，把每个前缀和sum[i]看作下标，出现过一次就在该位置+1；
那么对于每个r，其贡献就是坐标轴上[sum[r]-t ~ maxn]的值；

那么这个值咋算，由于每次都动态修改和查询，因此我们可以用树状数组/线段树；
我们可以开一个树状数组作为桶，维护值得前缀和，这样就能快速算出[sum[r]-t ~ maxn]的值；
ans += query(maxn-1) - query(get_num(sum[r] - t));

然后由于题目中前缀和作为下标太大，因此需要离散化；

注意：

1. 注意在离散化得时候就要把(sum[r] - t)一起离散化，因为要用到；
2. 注意树状数组要从1开始。
3. 注意这里0和-t是要用到的，所以也要离散化；
4. 注意当我们算第一个数的时候，0是可能产生贡献的，所以先update一下；

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 1e6 + 7;
const int N = 1e6 + 7;
const int M = 1e6 + 7;
const int mod = 3*5*7*11*13*17*19*23;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
inline int lowbit(int x) {return x & (-x);}

ll n,t;
ll a[maxn];
ll tr[maxn];
ll sum[maxn];
vector<ll> v;

inline int get_num(ll x)
{	//注意+1，树状数组从1开始
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}

inline void update(int x,int v)
{
	while(x < maxn)
	{
		tr[x] += v;
		x += lowbit(x);
	}	
}

inline ll query(int x)
{
	ll ans = 0;
	while(x)
	{
		ans += tr[x];
		x -= lowbit(x);
	}
	return ans;
}

int main()
{
	scanf("%lld %lld",&n,&t);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]), sum[i] = sum[i-1] + a[i];
	
	//离散化
	v.push_back(0);
	v.push_back(-t);
	for(int i=1;i<=n;i++)
	{
	    v.push_back(sum[i]);
	    v.push_back(sum[i]-t);
	}
	
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	
	update(get_num(0),1);
	ll ans = 0;
	for(int i=1;i<=n;i++)
	{
		ans += query(maxn-1) - query(get_num(sum[i] - t));
		
		update(get_num(sum[i]),1);
	}
	
	cout<<ans<<'\n';
	
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121