0分求条
查看原帖
0分求条
846041
__xxy_free_ioi__楼主2024/12/1 09:01
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10;

int n, L, R;
int ans;
int a[N], s[N], t[N];
vector<int> alls;

void add(int x, int d) {
	while (x <= n) {
		t[x] += d;
		x += (x & -x);
	}
}

int qurey(int x) {
	long long tot = 0;
	while (x) {
		tot += t[x];
		x -= (x & -x);
	}
	return tot;
}

signed main() {
	cin >> n >> L >> R;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
		alls.push_back(a[i]);
	}
	alls.push_back(0);
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(), alls.end()), alls.end());
	for (int i = 1; i <= n; i++) {
		s[i] = lower_bound(alls.begin(), alls.end(), s[i]) - alls.begin() + 1;
	}
	add(lower_bound(alls.begin() + 1, alls.end(), 0) - alls.begin() + 1, 1);
	for (int i = 1; i <= n; i++) {
		int l = lower_bound(alls.begin(), alls.end(), s[i] - R) - alls.begin() + 1,
			r = lower_bound(alls.begin(), alls.end(), s[i] - L) - alls.begin() + 1;
		ans += qurey(r) - qurey(l);
		add(s[i], 1);
	}
	cout << ans;
	return 0;
}
2024/12/1 09:01
加载中...