动态开点 求思路
查看原帖
动态开点 求思路
726139
残阳如血楼主2024/5/12 15:49

打算在 pushdown 的时候开左右两个儿子,但是好像没法获得每个儿子的区间之和。。

请问 pushdown 应该怎么写?

#include <vector>
#include <iostream>
typedef long long lint;
const int N = 1e5 + 10;

template <typename T>
struct Pool {
	std::vector<T *> buf;
	T *create() {
		buf.push_back(new T);
		return buf.back();
	}
	void dispose() {
		for (size_t i = 0; i < buf.size(); ++i) delete buf[i];
		buf.clear();
	}
};

struct TreeNode {
	int l, r;
	lint sum, lzy;
	TreeNode *lson, *rson;
};

int n, m;
lint a[N];

bool inRange(TreeNode *u, int L, int R) {
	return u->l >= L && u->r <= R;
}

bool outRange(TreeNode *u, int L, int R) {
	return u->l > R || u->r < L;
}

void maketag(TreeNode *u, lint x) {
	u->w += x * (u->r - u->l + 1);
	u->lzy += x;
}

void pushup(TreeNode *u) {
	u->w = u->lson->w + u->rson->w;
}

void pushdown(TreeNode *u) {
	
}

lint query(TreeNode *u, int L, int R) {
	if (outRange(u, L, R)) return 0;
	if (inRange(u, L, R)) return u->w;
	pushdown(u);
	return query(u->lson, L, R) + query(u->rson, L, R);
}

void update(TreeNode *u, int L, int R, lint x) {
	if (outRange(u, L, R)) return ;
	if (inRange(u, L, R)) { maketag(u, x); return ; }
	pushdown(u);
	update(u->lson, L, R, x);
	update(u->rson, L, R, x);
	pushup(u);
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cin >> n >> m;
	for (int i = 1; i <= n; ++i) std::cin >> a[i];
	return 0;
}
2024/5/12 15:49
加载中...