42pts,MLE,线段树求调
查看原帖
42pts,MLE,线段树求调
167697
BartAllen楼主2024/8/27 09:38
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 5;
const ll inf = 1e12;

ll n, p, root, tot, range, ans;
ll a[N], s[N], b[N];

struct Sgt {
	ll ls, rs;
	ll cnt;
	#define ls(p) t[p].ls
	#define rs(p) t[p].rs
	#define cnt(p) t[p].cnt
} t[N << 1];

//void discrete() {
//	for (int i = 0; i <= n; i++) b[i] = s[i];
//	sort(b, b + n + 1);
//	range = unique(b, b + n + 1) - b - 1;
//	for (int i = 0; i <= n; i++) s[i] = lower_bound(b, b + range + 1, s[i]) - b;
//}

void update(int p) {
	cnt(p) = cnt(ls(p)) + cnt(rs(p));
}

void change(ll &p, ll l, ll r, ll val, ll delta) {
	if (!p) p = ++tot;
	if (l == r) {
		cnt(p) += delta;
		return;
	}
	ll mid = l + r >> 1;
	if (val <= mid) change(ls(p), l, mid, val, delta);
	else change(rs(p), mid + 1, r, val, delta);
	update(p);
}

int ask(ll p, ll l, ll r, ll ql, ll qr) {
	if (!p) p = ++tot;
	if (ql <= l && qr >= r) {
		return cnt(p);
	}
	ll mid = l + r >> 1;
	ll val = 0;
	if (ql <= mid) val += ask(ls(p), l, mid, ql, qr);
	if (qr > mid) val += ask(rs(p), mid + 1, r, ql, qr);
	return val;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> p;
//	s[0] = -p;
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i] - p;
//	discrete();
	root = 1;
//	change(root, -inf, inf, s[0], 1);
	for (int i = 0; i <= n; i++) {
		ans += ask(root, -inf, inf, -inf, s[i]);
		change(root, -inf, inf, s[i], 1);
	}
	cout << ans << endl;
	return 0;
}
2024/8/27 09:38
加载中...