题解 | #F. 小红统计区间（hard）#

F. 小红统计区间（hard）

动态开点线段树的板子题, 直接贴板子, 每输入一个 就 update 一下, 查询时, 查询范围 Maxl (左极限值)到 范围的个数.

直接贴代码:

(有没有佬教教我, 成员函数内调用成员函数时, 不通过传入 tr 的引用, 调用 tr 的成员函数, 而是直接调用时为什么会爆栈)

#define int long long

const int Maxl = -1e14 - 10, Maxr = 1e14 + 10;
struct d_tree {
	struct op {
		int num, ls, rs;
	} tre[4000040];
	int cnt = 0;

	int build()//新建节点
	{	++cnt;
		tre[cnt].num = tre[cnt].ls = tre[cnt].rs = 0;
		return cnt;
	}

	int upd(int x, int pos, int val, d_tree &tr, int l = Maxl, int r = Maxr )
	{	if (!x)x = tr.build();
		if (l == r) {tre[x].num += val; return x;}
		int mid = (l + r) >> 1;
		if (pos <= mid)tre[x].ls = tr. upd(tre[x].ls, pos, val, tr, l, mid);
		if (pos > mid)tre[x].rs = tr.upd(tre[x].rs, pos, val, tr, mid + 1, r);
		tre[x].num = tre[tre[x].ls].num + tre[tre[x].rs].num;
		return x;
	}
	int ask(int x, int ql, int qr, d_tree &tr, int l = Maxl, int r = Maxr)
	{	if (!x)return 0;
		if (l >= ql && r <= qr) {
			return tre[x].num;
		}
		int mid = (l + r) >> 1, ans = 0;
		if (ql <= mid)ans += tr.ask(tre[x].ls, ql, qr, tr, l, mid);
		if (qr > mid)ans += tr.ask(tre[x].rs, ql, qr, tr, mid + 1, r);
		return ans;
	}
};

void solve(int _) {
	int n, k;
	cin >> n >> k;
	vector<int>a(n + 10);
	vector<int>pre(n + 10, 0);
	int ans = 0;
	d_tree tr;
	tr.build();
	tr.upd(1, 0, 1, tr);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
		ans += tr.ask(1, Maxl, pre[i] - k, tr);
		tr.upd(1, pre[i], 1, tr);

	}
	cout << ans << endl;
}