C++14(g++5.4) 解法, 执行用时: 153ms, 内存消耗: 11704K, 提交时间: 2019-12-08 20:06:19

#include <bits/stdc++.h>
using namespace std;
#define lowbit(i) i&(-i)
const int maxn = 2e5 + 7;
typedef long long ll;
int n;
ll sum[maxn<<1], a[maxn], m, b[maxn], v[maxn<<1], cnt;
void update(int x) {
    for (int i = x; i <= cnt; i += lowbit(i))
        sum[i]++;
}
ll getsum(int x) {
    ll ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans += sum[i];
    return ans;
}
int getid(ll x) {
    return lower_bound(v, v + cnt, x) - v + 1;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        b[i] = b[i - 1] + a[i];
        v[cnt++] = b[i];
        v[cnt++] = b[i] + m - 1;
    }
    v[cnt++] = 0; v[cnt++] = m - 1;
    sort(v, v + cnt);
    cnt = unique(v, v + cnt) - v;
    ll ans = 0;
    for (int i = n; i >= 0; i--) {
        ans += getsum(getid(b[i] + m - 1));
        update(getid(b[i]));
    }
    cout << ans << endl;
    return 0;
}

C++ 解法, 执行用时: 155ms, 内存消耗: 9736K, 提交时间: 2022-06-03 10:36:00

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
ll a[N],b[N],c[N<<1],sum[N<<1];
ll cnt;

void add(int x){
	while(x<=cnt){
		++sum[x];
		x+=x&-x;
	}
}

ll query(int x){
	ll ans=0;
	while(x){
		ans+=sum[x];
		x-=x&-x;
	}
	return ans;
}

int id(ll x){
	return lower_bound(c,c+cnt,x)-c+1;
}

int main (){
	int n;
	ll m;
	cin >> n >> m;
	for(int i=1; i<=n; ++i){
		cin >> a[i];
		b[i]=b[i-1]+a[i];
		c[cnt++]=b[i];
		c[cnt++]=b[i]+m-1;
	}
	c[cnt++]=0;	c[cnt++]=m-1;
	sort(c,c+cnt);
	cnt=unique(c,c+cnt)-c;
	ll ans=0;
	for(int i=n; i>=0; --i){
		ans+=query(id(b[i]+m-1));
		add(id(b[i]));
	} 
	cout << ans << endl;
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 109ms, 内存消耗: 9732K, 提交时间: 2023-03-13 21:01:30

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll a[N],b[N],v[N*2],w[N*2];
ll n,m,cnt=0;
void add(int x){
	while(x<=cnt){
		w[x]+=1;
		x+=x&-x;
	}
} 
ll query(int x){
	ll ans=0;
	while(x){
		ans+=w[x];
		x-=x&-x;
	}
	return ans;
} 
int getnum(ll x){
	return lower_bound(v,v+cnt,x)-v+1;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",a+i);
		b[i]=b[i-1]+a[i];
		v[cnt++]=b[i];
		v[cnt++]=b[i]+m-1;
	}
	v[cnt++]=0;v[cnt++]=m-1;
	sort(v,v+cnt);
	cnt=unique(v,v+cnt)-v;
	ll ans=0;
	for(int i=n;i>=0;i--){
		ans+=query(getnum(b[i]+m-1));
		add(getnum(b[i]));
	}
	printf("%lld\n",ans);
	return 0;
 }