@zzzc18
2017-06-23T17:37:22.000000Z
字数 1679
阅读 1240
线段树
orz几乎一遍写不对
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 100009
#define LL long long
LL a[MAXN];
LL n,m;
class Segment_Tree{
private:
LL cnt;
struct T{
LL ls,rs,left_range,right_range,sum,lazy;
};
T tree[MAXN<<1];
LL seglen(LL x){
return tree[x].right_range-tree[x].left_range+1;
}
void update(LL x){
tree[x].sum=tree[tree[x].ls].sum+tree[tree[x].rs].sum;
}
void pushdown(LL x){
if(tree[x].lazy){
if(tree[x].ls){
tree[tree[x].ls].lazy+=tree[x].lazy;
tree[tree[x].ls].sum+=tree[x].lazy*seglen(tree[x].ls);
}
if(tree[x].rs){
tree[tree[x].rs].lazy+=tree[x].lazy;
tree[tree[x].rs].sum+=tree[x].lazy*seglen(tree[x].rs);
}
}
tree[x].lazy=0;
}
public:
LL Build(LL l,LL r){
LL now=++cnt;
tree[now].left_range=l;tree[now].right_range=r;
if(l==r){
tree[now].sum=a[l];
return now;
}
LL mid=(l+r)>>1;
tree[now].ls=Build(l,mid);
tree[now].rs=Build(mid+1,r);
update(now);
return now;
}
void addnum(LL now,const LL &l,const LL &r,const LL &v){
pushdown(now);
if(l<=tree[now].left_range && tree[now].right_range<=r){
tree[now].sum+=v*seglen(now);
tree[now].lazy+=v;
return;
}
LL mid=(tree[now].left_range+tree[now].right_range)>>1;
if(l<=mid) addnum(tree[now].ls,l,r,v);
if(r>=mid+1) addnum(tree[now].rs,l,r,v);
update(now);
}
LL r2n(LL now,const LL &l,const LL &r){
pushdown(now);
if(l<=tree[now].left_range && tree[now].right_range<=r){
return tree[now].sum;
}
LL mid=(tree[now].left_range+tree[now].right_range)>>1;
LL re=0;
if(l<=mid) re+=r2n(tree[now].ls,l,r);
if(r>=mid+1) re+=r2n(tree[now].rs,l,r);
update(now);
return re;
}
}Seg;
int main(){
scanf("%lld%lld",&n,&m);
LL i;
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
Seg.Build(1,n);
for(i=1;i<=m;i++){
LL opt,l,r,x;
scanf("%lld%lld%lld",&opt,&l,&r);
if(opt==1){
scanf("%lld",&x);
Seg.addnum(1,l,r,x);
}
else
printf("%lld\n",Seg.r2n(1,l,r));
}
return 0;
}