CSES_1735WA.cpp

#include <iostream>
#include <cassert>
#include <algorithm>
#include <cstring>
#define LC(n) (((n) << 1) + 1)
#define RC(n) (((n) << 1) + 2)
#define ll long long
using namespace std;
const int LOGN = 20, max_v = (1 << LOGN)*4;
ll sum[max_v], add[max_v], set[max_v], arr[max_v];
bool lz[max_v];
int n, q, s = 1;

void push_down(int k, int L, int R){
    if(L + 1 == R) return ;
    if(lz[k]){
        int mid = (L + R)/2;
        set[LC(k)] = set[RC(k)] = set[k];
        sum[LC(k)] = sum[RC(k)] = (ll)(mid - L) * set[k];
        add[LC(k)] = add[RC(k)] = 0ll;
        set[k] = lz[k] = 0ll;
        lz[LC(k)] = lz[RC(k)] = 1;
    }
}

void U(int qL, int qR, int k, int op, ll val, int L, int R){
    if(qR <= L || R <= qL || R <= L) return ;
    if(qL <= L && R <= qR){
        if(op == 2){//set
            add[k] = 0ll;
            sum[k] = (ll)(R - L) * val;
            set[k] = val;
            lz[k] = 1;
        }else{
            add[k] += val;
        }
        return ;
    }
    push_down(k, L, R);
    int mid = (L + R)/2;
    U(qL, qR, LC(k), op, val, L, mid);
    U(qL, qR, RC(k), op, val, mid, R);
    sum[k] = sum[LC(k)] + sum[RC(k)] + (ll)(R - mid) * (add[LC(k)] + add[RC(k)]);
}

ll S(int qL, int qR, int k, int L, int R){
    if(qR <= L || R <= qL || R <= L) return 0ll;
    if(qL <= L && R <= qR) return add[k]*(ll)(R - L) + sum[k];
    push_down(k, L, R);
    int mid = (L + R)/2;
    return S(qL, qR, LC(k), L, mid) + S(qL, qR, RC(k), mid, R);
}

void precomp(){
    for(int i = s - 1; i<s + n - 1; i++){
        sum[i] = arr[i - (s - 1)];
    }
    for(int i = s - 2; i >= 0; i--){
        sum[i] = sum[LC(i)] + sum[RC(i)];
    }
}


int main(){
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> q;
    while(s<=n) s <<= 1; s <<=1;
    for(int i = 0; i<n; i++){
        cin >> arr[i];
    }
    precomp();
    while(q--){
        int op; cin >> op;
        if(op == 3){
            int a, b; cin >> a >> b;
            cout << S(a - 1, b, 0, 0, s) << '\n';
            cout.flush();
        }else{
            int a, b; ll c;
            cin >> a >> b >> c;
            U(a - 1, b, 0, op, c, 0, s);
        }
    }
    return 0;
}