社区讨论
莫名红9个?!蒟蒻求助qwq
P3372【模板】线段树 1参与者 4已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @mi86f33b
- 此快照首次捕获于
- 2025/11/21 09:23 4 个月前
- 此快照最后确认于
- 2025/11/21 09:52 4 个月前
手 打 的 线 段 树 模 板 !
上代码:
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];
}
}
回复
共 15 条回复,欢迎继续交流。
正在加载回复...