社区讨论

莫名红9个?!蒟蒻求助qwq

P3372【模板】线段树 1参与者 4已保存回复 15

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
15 条
当前快照
1 份
快照标识符
@mi86f33b
此快照首次捕获于
2025/11/21 09:23
4 个月前
此快照最后确认于
2025/11/21 09:52
4 个月前
查看原帖

手 打 的 线 段 树 模 板 !

(但是不知道为什么wa了9个点)
上代码:
CPP
#include <bits/stdc++.h>

using namespace std;

template<typename T1>
struct LineTree{
	T1* datas;
	T1* lazy_tag;
	T1* count;
	T1* in;
	int* size;
	
	LineTree(const T1&, const int&);
	~LineTree();
	
	void Build(int, int, int);
	void Upgrade(int, int, int, int, int);
	void Upgrade(int, int, int, int, int, int);
	void PushUp(int);
	void PushDown(int, int);
	void In();
	T1 Sum(int, int, int, int, int);
};

int main(int argc, char* argv[]){
	register int* n = new int;
	register int* m = new int;
	cin >> *n >> *m;
	LineTree<long long> t(1, *n);
	register long long* cmd = new long long;
	register long long* x = new long long;
	register long long* y = new long long;
	register long long* k = new long long;
	t.In();
	t.Build(1, *n, 1);
	for(register long long i = 0; i < *m; i++){
		cin >> *cmd;
		if(*cmd & 1){
			cin >> *x >> *y >> *k;
			t.Upgrade(*x, *y, *k, 1, *n, 1);
		}
		else{
			cin >> *x >> *y;
			cout << t.Sum(*x, *y, 1, *n, 1) << endl;
		}
		*x = 0;
		*y = 0;
		*k = 0;
	}
	delete n;
	delete m;
	delete cmd;
	delete x;
	delete y;
	delete k;
	return 0;
} 

template<typename T1>
LineTree<T1>::LineTree(const T1& mainCount, const int& sz){
	this->datas = new T1[4 * sz];
	this->lazy_tag = new T1[4 * sz];
	this->count = new T1;
	this->size = new int;
	this->in = new T1[4 * sz];
	*this->count = mainCount;
	*this->size = sz;
}

template<typename T1>
LineTree<T1>::~LineTree(){
	delete this->datas;
	delete this->lazy_tag;
	delete this->count;
	delete this->size;
	delete this->in;
}

template<typename T1>
void LineTree<T1>::Build(int left, int right, int root){
	this->lazy_tag[root] = 0;
	if(left == right){	//找到叶节点 
		this->datas[root] = this->in[left];	//设为单位值
		return;	//退出 
	}
	else{
		int mid = (right + left) / 2;	//二分 
		this->Build(left, mid, root * 2);	//左子树 
		this->Build(mid + 1, right, root * 2 + 1);	//右子树 
		this->PushUp(root);	//回溯更新 
	}
}

template<typename T1>
void LineTree<T1>::Upgrade(int point, int data, int left, int right, int root){
	if(left == right){		//找到该节点 
		this->datas[root] += data;	//更新 
		return;	//结束 
	}
	else{
		int mid = (right + left) / 2;	 
		if(point < mid){
			this->Upgrade(point, data, mid + 1, right, root * 2 + 1);
		} 
		else{
			this->Upgrade(point, data, left, mid, root * 2);
		}
		//二分找[point,point] 
		this->PushUp(root);
		//回溯,更新父节点 
	}
}

template<typename T1>
void LineTree<T1>::Upgrade(int from, int to, int data, int left, int right, int root){
	if(from <= left && to >= right){	//在需更新范围内 
		this->datas[root] += (right - left + 1) * data;	//更新总的区间值 
		this->lazy_tag[root] += data;	//设好lazy_tag,过后再改 
		return;	//退出 
	}
	else{
		this->PushDown(root, right - left + 1);	//下推root 
		T1 mid = (left + right) / 2;
		if(from <= mid){
			this->Upgrade(from, to, data, left, mid, root * 2);
		}
		if(to > mid){
			this->Upgrade(from, to, data, mid + 1, right, root * 2 + 1);
		}
		this->PushUp(root);
		//还是二分回溯 
	}
}

template<typename T1>
void LineTree<T1>::PushUp(int root){
	this->datas[root] = this->datas[root * 2] + this->datas[root * 2 + 1];
} 

template<typename T1>
void LineTree<T1>::PushDown(int root, int length){
	if(this->lazy_tag[root] == 0) return;
	else{
		this->lazy_tag[root * 2] += this->lazy_tag[root];
		this->lazy_tag[root * 2 + 1] += this->lazy_tag[root];
		this->datas[root * 2] += this->lazy_tag[root * 2] * (length - (length / 2));
		this->datas[root * 2 + 1] += this->lazy_tag[root * 2 + 1] * (length / 2);
		this->lazy_tag[root] = 0;
	}
}

template<typename T1>
T1 LineTree<T1>::Sum(int from, int to, int left, int right, int root){
	if(left >= from && right <= to){
		return this->datas[root];
	}
	else{
		this->PushDown(root, right - left + 1);
		T1 mid = (right + left) / 2;
		T1 ans = 0;
		if(from <= mid){
			ans += this->Sum(from, to, left, mid, root * 2);
		}
		if(to > mid){
			ans += this->Sum(from, to, mid + 1, right, root * 2 + 1);
		}
		return ans;
	}
}

template<typename T1>
void LineTree<T1>::In(){
	for(register int i = 1; i <= *size; i++){
		cin >> this->in[i];
	}
}
QwQ本蒟蒻彻底自闭

回复

15 条回复,欢迎继续交流。

正在加载回复...