线段树10ptsac#1求调

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
int tree[400010],lztag[400010];
int lson(int i){
    return i<<1;
}
int rson(int i){
    return (i<<1)+1;
}
void push_down(int point,int x,int y){
    if(!lztag[point])return;
    tree[point]+=(y-x+1)*lztag[point];
    lztag[lson(point)]+=lztag[point];
    lztag[rson(point)]+=lztag[point];
    lztag[point]=0;
    return;
}
void push_up(int point){
    int fa=point>>1;
    tree[fa]=tree[lson(fa)]+tree[rson(fa)];
    return;
}
void add(int x,int y,int nowx,int nowy,int k,int point){
    if(x<=nowx&&nowy<=y){
        lztag[point]+=k;
        push_down(point,nowx,nowy);
        push_up(point);
        return;
    }
    int mid=(nowx+nowy)>>1;
    if(x<=mid)add(x,y,nowx,mid,k,lson(point));
    if(y>mid)add(x,y,mid+1,nowy,k,rson(point));
    push_up(point);
    return;
}
int check(int x,int y,int nowx,int nowy,int point){
    push_down(point,nowx,nowy);
    push_up(point);
    if(x<=nowx&&nowy<=y){
//      cout<<"ahjsdof"<<nowx<<' '<<nowy<<" "<<tree[point]<<"lazy:"<<lztag[point]<<endl;
        push_up(point);
        return tree[point];
    }
    int mid=(nowx+nowy)>>1;
    int a=0,b=0;
    if(x<=mid)a=check(x,y,nowx,mid,lson(point));
    if(y>mid)b=check(x,y,mid+1,nowy,rson(point));
//  cout<<"ahjsdof"<<nowx<<' '<<nowy<<" "<<a<<' '<<b<<endl;
    return a+b;
}
main(){
    int n,m;
    cin>>n>>m;
    int x,y,k;
    for(int i=1;i<=n;i++){
        cin>>x;
        add(i,i,1,n,x,1);
//      for(int i=1;i<=4*n;i++){
//          cout<<tree[i]<<' '<<lztag[i]<<endl;
//      }
    }
    for(int i=1;i<=m;i++){
        int c;
        cin>>c;
        switch(c){
            case 1:{
                cin>>x>>y>>k;
                add(x,y,1,n,k,1); 
                break;
            }
            case 2:{
                cin>>x>>y;
                int a=check(x,y,1,n,1);
                printf("%lld\n",a);
                break;
            }
        }
//      for(int i=1;i<=4*n;i++){
//          cout<<tree[i]<<' '<<lztag[i]<<endl;
//      }
    }
    return 0;
}