题意：
给出一个数组，元素有正有负有0，问其区间和小于 t 的子区间的个数。
sum[ r ]-sum[ l-1 ]<t，其中sum是a的前缀和。
实现的方法就是从前往后对于每一个sum[ i ]，看在它前面有多少个大于等于sum[ i ] - t 的前缀和。
树状数组维护的是 i 前面有几个数小于等于它
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <cmath> 5 #include <algorithm> 6 #include <set> 7 #include <iostream> 8 #include <map> 9 #include <stack> 10 #include <string> 11 #include <vector> 12 #include <bits/stdc++.h> 13 #define pi acos(-1.0) 14 #define eps 1e-9 15 #define fi first 16 #define se second 17 #define rtl rt<<1 18 #define rtr rt<<1|1 19 #define bug printf("****** ") 20 #define mem(a,b) memset(a,b,sizeof(a)) 21 #define name2str(x) #x 22 #define fuck(x) cout<<#x" = "<<x<<endl 23 #define f(a) a*a 24 #define sf(n) scanf("%d", &n) 25 #define sff(a,b) scanf("%d %d", &a, &b) 26 #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) 27 #define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d) 28 #define pf printf 29 #define FRE(i,a,b) for(i = a; i <= b; i++) 30 #define FREE(i,a,b) for(i = a; i >= b; i--) 31 #define FRL(i,a,b) for(i = a; i < b; i++)+ 32 #define FRLL(i,a,b) for(i = a; i > b; i--) 33 #define FIN freopen("data.txt","r",stdin) 34 #define gcd(a,b) __gcd(a,b) 35 #define lowbit(x) x&-x 36 #define rep(i,a,b) for(int i=a;i<b;++i) 37 #define per(i,a,b) for(int i=a-1;i>=b;--i) 38 using namespace std; 39 typedef long long LL; 40 typedef unsigned long long ULL; 41 const int INF = 0x3f3f3f3f; 42 const LL INFLL = 0x3f3f3f3f3f3f3f3fLL; 43 const int maxn = 2e5 + 7; 44 int n; 45 LL a[maxn], sum[maxn], t, cnt[maxn], c[maxn]; 46 void update ( int pos, LL x ) { 47 while ( pos <= n + 1 ) { 48 c[pos] += x; 49 pos += lowbit ( pos ); 50 } 51 } 52 LL getsum ( int pos ) { 53 LL sum = 0; 54 while ( pos > 0 ) { 55 sum += c[pos]; 56 pos -= lowbit ( pos ); 57 } 58 return sum; 59 } 60 int main() { 61 scanf ( "%d%lld", &n, &t ); 62 for ( int i = 1 ; i <= n ; i++ ) { 63 scanf ( "%lld", &a[i] ); 64 sum[i] = sum[i - 1] + a[i]; 65 cnt[i] = sum[i]; 66 } 67 sort ( cnt, cnt + n + 1 ); 68 LL ans = 0; 69 for ( int i = 1 ; i <= n ; i++ ) { 70 int pos = lower_bound ( cnt, cnt + n + 1, sum[i - 1] ) - cnt + 1;//树状数组下标不能是0 所以需要将下标++ 71 update ( pos, 1 ); 72 pos = lower_bound ( cnt, cnt + n + 1, sum[i] - t + 1 ) - cnt; //求有多少个数小于等于sum[i] - t 73 ans += ( i - getsum ( pos ) );//区间的总数是 i-1 小于等于的个数是 getsum ( pos ) - 1 74 } 75 printf ( "%lld ", ans ); 76 return 0 ; 77 }