社区讨论
人麻了,自己封装的板子怎么不对呢
P3372【模板】线段树 1参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mhjrbvo3
- 此快照首次捕获于
- 2025/11/04 07:14 4 个月前
- 此快照最后确认于
- 2025/11/04 07:14 4 个月前
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class Info>
struct SGT{
int n;
vector<int>tag;
vector<Info>info;
SGT (vector<Info>&init){
n=init.size();
info.assign(n*4,Info());
tag.assign(n*4,0);
function<void(int,int,int)>build=[&](int p,int l,int r){
info[p]={l,r,0};
if(l==r){
info[p]=init[l];
return;
}
int mid=l+r>>1;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
pull(p);
};
build(1,1,n);
}
void pull(int p){
info[p]=info[2*p]+info[2*p+1];
}
void add(int p,int v){
tag[p]+=v;
info[p].sum+=(info[p].r-info[p].l+1)*v;
}
void push(int p){
add(2*p,tag[p]);
add(2*p+1,tag[p]);
tag[p]=0;
}
Info query(int p,int nowl,int nowr,int l,int r){
if(nowl>r||nowr<l){
return {};
}
if(nowl>=l&&nowr<=r){
return info[p];
}
push(p);
int mid=(nowl+nowr)/2;
return query(2*p,nowl,mid,l,r)+query(2*p+1,mid+1,nowr,l,r);
}
Info query(int l,int r){
return query(1,1,n,l,r);
}
void rangeadd(int p,int nowl,int nowr,int l,int r,int v){
if(nowl>r||nowr<l){
return;
}
if(nowl>=l&&nowr<=r){
add(p,v);
return;
}
int mid=nowl+nowr>>1;
push(p);
rangeadd(2*p,nowl,mid,l,r,v);
rangeadd(2*p+1,mid+1,nowr,l,r,v);
pull(p);
}
void rangeadd(int l,int r,int v){
rangeadd(1,1,n,l,r,v);
}
};
struct Info{
int l,r;
int sum=0;
};
Info operator+(const Info&a,const Info&b){
Info tem;
tem.sum=a.sum+b.sum;
return tem;
}
void solve(){
int n,q;cin>>n>>q;
vector<Info>a(n+1);
for(int i=1;i<=n;i++){
int x;cin>>x;
a[i]={i,i,x};
}
SGT<Info>sgt(a);
while(q--){
int op;cin>>op;
if(op==1){
int l,r,v;cin>>l>>r>>v;
sgt.rangeadd(l,r,v);
}else{
int l,r;cin>>l>>r;
cout<<sgt.query(l,r).sum<<"\n";
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T=1;
//cin>>T;
while(T--){
solve();
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...