ILoveSoviet @ 2023-07-12 22:42:49
#include<iostream>
using namespace std;
int n,dat[100005];
struct node{
int l,r,dat,lazy;
}tree[100005];
inline int ll(int i){return i*2;}
inline int rr(int i){return i*2+1;}
inline void nex(int d){
if(tree[d].l==tree[d].r){
tree[d].dat+=tree[d].lazy;
tree[d].lazy=0;
return;
}
tree[d].dat+=tree[d].lazy*(tree[d].r-tree[d].l+1);
tree[ll(d)].lazy+=tree[d].lazy;
tree[rr(d)].lazy+=tree[d].lazy;
tree[d].lazy=0;
}
void make_tree(int d,int l,int r){
tree[d].l=l;
tree[d].r=r;
if(l==r){
tree[d].dat=dat[l];
}
else{
int mid=(l+r)/2;
make_tree(ll(d),l,mid);
make_tree(rr(d),mid+1,r);
tree[d].dat=tree[ll(d)].dat+tree[rr(d)].dat;
}
}
int find_a_dat(int i,int d){
nex(d);
// cout<<d<<" ";
int l=tree[d].l,r=tree[d].r;
if(l==r&&r==i){
return tree[d].dat;
}
int mid=(l+r)/2;
if(i<=mid) return find_a_dat(i,ll(d));
else if(i>mid) return find_a_dat(i,rr(d));
}
void add_a_dat(int i,int d,int add){
nex(d);
// cout<<i<<" ";
int l=tree[d].l,r=tree[d].r;
if(l==r){
tree[d].dat+=add;
return;
}
int mid=(l+r)/2;
if(i<=mid) add_a_dat(i,ll(d),add);
else if(i>mid) add_a_dat(i,rr(d),add);
tree[d].dat=tree[ll(d)].dat+tree[rr(d)].dat;
}
int find_a_line(int d,int l,int r){
nex(d);
int l1=tree[d].l,r1=tree[d].r;
if(l1==l&&r1==r) return tree[d].dat;
int mid=(l1+r1)/2;
if(mid<l) return find_a_line(rr(d),l,r);
else if(mid>=r) return find_a_line(ll(d),l,r);
else return find_a_line(ll(d),l,mid)+find_a_line(rr(d),mid+1,r);
}
void add_a_line(int d,int l,int r,int add){
nex(d);
int l1=tree[d].l,r1=tree[d].r;
if(l1==l&&r1==r){
tree[d].lazy+=add;
nex(d);
return;
}
int mid=(l1+r1)/2;
if(mid<l) add_a_line(rr(d),l,r,add);
else if(mid>=r) add_a_line(ll(d),l,r,add);
else add_a_line(ll(d),l,mid,add),add_a_line(rr(d),mid+1,r,add);
tree[d].dat=tree[ll(d)].dat+tree[rr(d)].dat;
}
int main(){
int n;
cin>>n;
int p;
cin>>p;
for(int i=1;i<=n;i++){
cin>>dat[i];
}
make_tree(1,1,n);
while(p--){
int op;
cin>>op;
// if(op==0){
// int v;
// cin>>v;
// cout<<find_a_dat(v,1);
// }
// else if(op==1){
// int v,add;
// cin>>v>>add;
// add_a_dat(v,1,add);
// }
if(op==2){
int l,r;
cin>>l>>r;
cout<<find_a_line(1,l,r)<<endl;
}
else if(op==1){
int l,r,add;
cin>>l>>r>>add;
add_a_line(1,l,r,add);
}
}
}
万分感谢!
by OldDriverTree @ 2023-07-12 22:51:59
@ILoveSoviet 没 pushdown 呀
by suzhikz @ 2023-07-12 22:55:22
@OldDriverTree 头像真好看
by WsW_ @ 2023-07-12 23:06:02
?这是动态开点吗?