维护区间和,两个操作:一个是将某个区间设置成一个值,一个是将某个区间增加一个固定值
/**************************************************************/
每走到一个区间就把lazy tag下放。下放的时候注意顺序!
#include <cstdio>
#include <cstring>
const int N = ;
struct NODE{
int l,r;
int sum;
int setTo,add;
NODE(){setTo=add=;}
int length(){return (r-l+);}
};
int data[N];
NODE segtree[N*]; void build(int id,int l,int r){
segtree[id].l = l;
segtree[id].r = r;
if(l==r){
segtree[id].sum = data[l];
return ;
}
int mid = (l+r)>>;
build(id*+,l,mid);
build(id*+,mid+,r);
segtree[id].sum = segtree[id*+].sum+segtree[id*+].sum;
} void modify(int id,int spos,int epos,int value,int type){
if(segtree[id].l==spos&&segtree[id].r==epos){
if(type){
segtree[id].setTo = value;
segtree[id].add = ;
segtree[id].sum = segtree[id].length()*value;
}
else{
segtree[id].add += value;
segtree[id].sum += segtree[id].length()*value;
}
return ;
} //push down
if(segtree[id].setTo){
segtree[id*+].setTo=segtree[id*+].setTo=segtree[id].setTo;
segtree[id*+].add=segtree[id*+].add=;
segtree[id*+].sum = segtree[id*+].length()*segtree[id*+].setTo;
segtree[id*+].sum = segtree[id*+].length()*segtree[id*+].setTo;
segtree[id].setTo = ;
}
if(segtree[id].add){
segtree[id*+].add += segtree[id].add;
segtree[id*+].add += segtree[id].add;
segtree[id*+].sum += segtree[id*+].length()*segtree[id].add;
segtree[id*+].sum += segtree[id*+].length()*segtree[id].add;
segtree[id].add = ;
} int mid = (segtree[id].l+segtree[id].r)>>;
if(epos<=mid) modify(id*,spos,epos,value,type);
else if(spos>mid) modify(id*+,spos,epos,value,type);
else{
modify(id*+,spos,mid,value,type);
modify(id*+,mid+,epos,value,type);
} segtree[id].sum = segtree[id*+].sum+segtree[id*+].sum;
}
int main(){
int n,t;
scanf("%d%d",&n,&t); n++;
for(int i=;i<=n;i++) scanf("%d",data+i);
build(,,n);
while(t--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
modify(,b+,c+,d,a);
printf("%d\n",segtree[].sum);
}
return ;
}