80pts警示后人
查看原帖
80pts警示后人
376083
White_AL楼主2024/1/2 18:19
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
int n;
ll l, r;
ll pre[MAXN];
ll d[MAXN];		//离散化数组 
struct bitIndexedTree {
	ll t[MAXN * 2];
	int lowbit(int x) {
		return x & (-x);
	}
	ll query(int p) {
		if (p <= 0) return 0;
		ll res = 0; 
		for (int i = p; i > 0; i -= lowbit(i)) {
			res += t[i];
		}
		return res;
	}
	void change(int p, ll x) {
		for (int i = p; i <= n + 10; i += lowbit(i)) {
			t[i] += x;
		}
	}
} bit;
signed main() {
	scanf("%lld%lld%lld", &n, &l, &r);
	++n;
	for (int i = 2; i <= n; ++i) {
		ll t;
		scanf("%lld", &t);
		pre[i] = pre[i - 1] + t;
		d[i] = pre[i];
	}
	sort(d + 1, d + n + 1);
	int dcnt = unique(d + 1, d + n + 1) - d - 1;
	for (int i = 1; i <= n; ++i) pre[i] = lower_bound(d + 1, d + dcnt + 1, pre[i]) - d;
	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		bit.change(pre[i], 1);
		int up = upper_bound(d + 1, d + dcnt + 1, d[pre[i]] - l) - d - 1;
		int down = lower_bound(d + 1, d + dcnt + 1, d[pre[i]] - r) - d - 1;
		ans += bit.query(up) - bit.query(down);
		if (l == 0) --ans;
	}
	printf("%lld\n", ans);
	return 0;
} 

树状数组做法 如果没过测试点5&10 请注意l=0时需要减去一个也不选的情况

2024/1/2 18:19
加载中...