树状数组求条QWQpts
查看原帖
树状数组求条QWQpts
681558
Weizhuo_Zhao楼主2024/11/29 14:04
#include <bits/stdc++.h>
#define MAX_N 100005
using namespace std;
int n, k, a[MAX_N], b[MAX_N], c[MAX_N];
pair<int, int>s[MAX_N];

bool cmp(pair<int, int>x, pair<int, int>y) {
	return x.first == y.first ? x.second > y.second : x.first > y.first;
}

int lowbit(int x) {
	return -x & x;
}

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

int sum(int x) {
	int s = 0;
	for (; x > 0; x -= lowbit(x))
		s += c[x];
	return s;
}
long long ans;

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		b[i] = a[i] - k;
	for (int i = 1; i <= n; i++) {
		s[i].first = s[i - 1].first + b[i];
		s[i].second = i;
	}
	sort(s + 1, s + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		add(s[i].second, 1);
		ans += sum(s[i].second - 1);
	}
	cout << ans;
	return 0;
}
2024/11/29 14:04
加载中...