用的是结构体写法
WA数据:
输入
8 10 640 591 141 307 942 58 775 133 2 1 5 2 3 8 2 3 6 2 5 8 2 4 8 1 4 8 60 2 1 6 2 5 8 1 3 7 15 1 2 6 86
输出
2621 2356 1448 1908 2215 2859 2148
代码如下:
照片版: 文字版:
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,q,w[maxn];
struct tree{
int l,r,w=0,tag=0;
}t[4*maxn];
int ls(int p){
return p*2;
}
int rs(int p){
return p*2+1;
}
void push_up(int p){
t[p].w=t[ls(p)].w+t[rs(p)].w;
}
void addtag(int p,int w){
t[p].tag+=w;
t[p].w+=w*(t[p].r-t[p].l+1);
return;
}
void push_down(int p){
if(t[p].tag){
t[p].w+=t[p].tag;
addtag(ls(p),t[p].tag);
addtag(rs(p),t[p].tag);
t[p].tag=0;
}
}
void update(int l,int r,int p,int w){
int pl=t[p].l,pr=t[p].r;
if(l<=pl&&pr<=r){
addtag(p,w);
return;
}
push_down(p);
int mid=(pl+pr)>>1;
if(l<=mid)update(l,r,ls(p),w);
if(r>mid)update(l,r,rs(p),w);
push_up(p);
}
void init(int p,int l,int r){
t[p].l=l;t[p].r=r;
if(l==r){t[p].w=w[l];return;}
int mid=(l+r)>>1;
init(ls(p),l,mid);
init(rs(p),mid+1,r);
push_up(p);
}
int look(int l,int r,int p){
int pl=t[p].l,pr=t[p].r;
if(l<=pl&&pr<=r)return t[p].w;//如果包含此线段则加上
push_down(p);
int mid=(pl+pr)>>1;
return ((l<=mid) ? look(l,r,ls(p)) : 0)+((r>mid) ? look(l,r,rs(p)) : 0);
}
void put(){
for(int i=1;i<=4*n;i++){
if(t[i].l+t[i].r==0){
continue;
}
printf("p:%d,l:%d,r:%d,w:%d,tag:%d,ls:%d,rs:%d\n",i,t[i].l,t[i].r,t[i].w,t[i].tag,ls(i),rs(i));
}
}
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>w[i];
}
init(1,1,n);
for(int i=1;i<=q;i++){
int l,r,p,k;
cin>>p;
cin>>l>>r;
if(p==1){
cin>>k;
update(l,r,1,k);
// put();
}else{
cout<<look(l,r,1)<<'\n';
// put();
}
}
return 0;
}
//from chpyx2