20分/时不时30分求条

#include <bits/stdc++.h>
using namespace std ;
#define int long long 
#define over(i,a,b) for(int i = (int)a ; i <= (int)b ; i ++ )
const int N = 200010 ;
int n , m ;
int a[N] ; 
struct info{
    int val , tag = 0 , l , r ;
}seg[N * 4] ; 
void update(int id){
    seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val ; 
}
void pushtag(int id){
    if(seg[id].tag != 0 ){
        seg[id * 2].tag = seg[id].tag ; 
        seg[id * 2 + 1 ].tag = seg[id].tag ; 
        seg[id * 2].val += seg[id].tag * (seg[id * 2].r - seg[id * 2].l + 1) ; 
        seg[id * 2 + 1].val += seg[id].tag * (seg[id * 2 + 1].r - seg[id * 2 + 1].l + 1) ; 
        seg[id].tag = 0 ;
    }
}
void settag(int id , int val){
    seg[id].tag += val ; 
    seg[id].val += val * (seg[id].r - seg[id].l + 1) ; 
}
void build(int id , int l , int r ){
    seg[id].l = l , seg[id].r = r ; 
    if(l == r){
        seg[id].val = a[l] ; 
    }else{
        int mid = (l + r) / 2 ; 
        build(id * 2 , l , mid ) ; 
        build(id * 2 + 1 , mid + 1 , r) ; 
        update(id) ; 
    }
}
void modify(int id , int l , int r , int ql , int qr ,int val){
    if(l == ql && r == qr) settag(id,val) ;
    else{
        int mid = (l + r) / 2 ; 
        pushtag(id);
        if(qr <= mid) modify(id * 2 , l , mid , ql , qr , val) ; 
        else if(ql > mid) modify(id * 2 + 1 , mid + 1 , r , ql , qr , val) ; 
        else{
            modify(id * 2 , l , mid , ql , mid , val) ; 
            modify(id * 2 + 1 , mid + 1 , r , mid + 1 , qr , val) ; 
        }
        update(id) ; 
    }
}
int query(int id , int l , int r , int ql , int qr ){
    if(l == ql && r == qr){
        return seg[id].val ; 
    }else{
        pushtag(id) ;
        int mid = (l + r) / 2 ; 
        if(qr <= mid) return query(id * 2 , l , mid , ql , qr);
        else if(ql > mid) return query(id * 2 + 1 , mid + 1 , r , ql , qr ) ; 
        else{
            return  query(id * 2 , l , mid , ql , mid) + query(id * 2 + 1 , mid + 1 , r , mid + 1 , qr ) ; 
        }

    }
}
signed main (){
    cin >> n >> m ;
    over(i,1,n) cin >> a[i] ;
    build(1,1,n) ; 
    over(i,1,m){
        int t ; cin >> t ; 
        if(t == 1){
            int x , y , k ; cin >> x >> y >> k ;
            modify(1,1,n,x,y,k) ; 
        }else{
            int x , y ; cin >> x >> y ; 
            cout << query(1,1,n,x,y) << "\n" ; 
        }
    }
    return 0 ;
}