树状数组10pts求条
查看原帖
树状数组10pts求条
681558
Weizhuo_Zhao楼主2024/11/29 23:53
#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 h = 0;
	for (; x > 0; x -= lowbit(x))
		h += c[x];
	return h;
}
long long ans;

map<int, int>t;
set<int>qwq;
set<int>::iterator it;

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;
		qwq.insert(s[i].first);
		t[s[i].first]++;
	}
	sort(s + 1, s + n + 1, cmp);
	for (int i = 1; i <= n; i++) {
		ans += sum(s[i].second);
		add(s[i].second, 1);
	}
	for (it = qwq.begin(); it != qwq.end(); it++)
		ans += (t[*it] - 1) * t[*it] / 2;//这堆是因为s_i==s_j这个判断不到,就累加一下的,反正不一定对。。。
	cout << ans;
	return 0;
}

求你了,调调吧!都从22:00自己搞到24:00了,逆序对s_i>s_j会,等于不会!帮我看看吧!

2024/11/29 23:53
加载中...