我的线段树需要 8 倍空间!
  • 板块学术版
  • 楼主I_Love_DS
  • 当前回复10
  • 已保存回复10
  • 发布时间2024/11/28 21:45
  • 上次更新2024/11/29 08:21:04
查看原帖
我的线段树需要 8 倍空间!
1118614
I_Love_DS楼主2024/11/28 21:45

为什么?

#include <bits/stdc++.h>

using namespace std;

const int N = 60050;

int n, m, q;

struct SegmentTree {
	int v, tag;
} t[8 * N];

void pushdown(int k) {
	int x = t[k].tag;
	if (!x) return;
	t[k + k].v -= x;
	t[k + k].tag += x;
	t[k + k + 1].v -= x;
	t[k + k + 1].tag += x;
	t[k].tag = 0;
}

void pushup(int k) {
	t[k].v = min(t[k + k].v, t[k + k + 1].v);
}

void buildtree(int k, int l, int r) {
	if (l == r) {
		t[k].v = m;
		t[k].tag = 0;
		return;
	}
	int m = (l + r) / 2;
	buildtree(k + k, l, m);
	buildtree(k + k + 1, m + 1, r);
	pushup(k);
}

void insert(int k, int l, int r, int x, int y, int z) {
	if (l == x && r == y) {
		t[k].v -= z;
		t[k].tag += z;
		pushdown(k);
		//cerr << k << " " << t[k].v << endl;
		return;
	}
	pushdown(k);
	int m = (l + r) / 2;
	if (y <= m) insert(k + k, l, m, x, y, z);
	else if (x > m) insert(k + k + 1, m + 1, r, x, y, z);
	else insert(k + k, l, m, x, m, z), insert(k + k + 1, m + 1, r, m + 1, y, z);
	pushup(k);
	//cerr << k << " " << t[k].v << endl;
}

int calc(int k, int l, int r, int x, int y) {
	if (l == x && r == y) return t[k].v;
	pushdown(k);
	int m = (l + r) / 2, ans = 1 << 30;
	if (y <= m) ans = calc(k + k, l, m, x, y);
	else if (x > m) ans = calc(k + k + 1, m + 1, r, x, y);
	else ans = min(calc(k + k, l, m, x, m), calc(k + k + 1, m + 1, r, m + 1, y));	
	pushup(k);
	return ans;
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	--n;
	buildtree(1, 1, n);
	while (q--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		--y;
		int d = calc(1, 1, n, x, y);
		//cerr << d << endl;
		if (d < z) printf("N\n");
		else {
			printf("T\n");
			insert(1, 1, n, x, y, z);
		}
	}
	return 0;
}
2024/11/28 21:45
加载中...