5r树状数组求调
查看原帖
5r树状数组求调
486799
BlackPanda楼主2023/6/3 17:05
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

#define lowbit(x) x&(-x)
#define int long long

int n, m, t;
int C[N], a[N], b[N], s[N];

void add(int x, int c)
{
	for (int i = x; i <= n; i += lowbit(i))
		C[i] += c;
}

int ask(int x)
{
	int res = 0;
	for (int i = x; i >= 1; i -= lowbit(i))
		res += C[i];
	return res;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin >> n >> t;
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
		b[i] = s[i];
	}
	sort(b + 1, b + n + 1);
	long long res = 0;
	for (int i = 1; i <= n; i ++ )
	{
		int k = lower_bound(b + 1, b + n + 1, s[i - 1]) - b;
		add(k, 1);
		k = lower_bound(b + 1, b + n + 1, s[i] - t) - b;
		res += i - ask(k);
	}
	cout << res << endl;
	return 0;
}
2023/6/3 17:05
加载中...