【每日一题】3月2日区区区间

题意

这个题目线段树三个字都写在题目上了 就没啥好说的了 就是在普通的修改上加上了一个等差数列 因此我们在用lazy维护的时候 可以给lazy打上首项的值 然后其他的就是一个等差数列 在计算的时候也可以通过来判断等差数列的长度 这样知道首项知道等差数列的长度 就可以维护了 然后求和就是用等差数列求和来求即可

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 2e5 + 7;
const int INF = 0x3f3f3f3f;

int n , m ;
int a[N];
ll sum[N << 2] , lazy[N << 2];  

ll calc(ll a1 , ll n){
    return (a1 + a1 + n - 1) * n / 2;
}

void push_up(int rt){
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void push_down(int rt , int l , int r){
    int mid = (l + r) >> 1;
    if(lazy[rt]){
        lazy[rt << 1] = lazy[rt];
        lazy[rt << 1 | 1] = lazy[rt] + (mid - l + 1);
        sum[rt << 1] = calc(lazy[rt << 1] , mid - l + 1);
        sum[rt << 1 | 1] = calc(lazy[rt << 1 | 1] , r - mid);
        lazy[rt] = 0;
    }
}


void update(int rt , int l , int r , int L , int R , int k){
    if(L <= l && r <= R){
        ll a1 = k + l - L , n  = r - l + 1;
        lazy[rt] = a1;
        sum[rt] = calc(a1 , n);
        return ;
    }
    push_down(rt , l , r);
    int mid = (l + r) >> 1 ;
    if(L <= mid) update(rt << 1 , l , mid , L , R , k);
    if(R > mid) update(rt << 1 | 1 , mid + 1, r , L , R , k);
    push_up(rt);
}

ll query(int rt , int l , int r , int L , int R){
    if(L <= l && r <= R )   return sum[rt];
    push_down(rt , l , r);
    ll res = 0;
    int mid = (l + r) >> 1;
    if(L <= mid)    res += query(rt << 1, l , mid , L , R);
    if(R > mid)     res += query(rt << 1 | 1 ,  mid + 1 , r , L ,R);
    return res;
}
void build(int rt , int l , int r){
    if(l == r){
        sum[rt] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(rt << 1 , l , mid);
    build(rt << 1 | 1 , mid + 1 , r);
    push_up(rt);
}

int main(void){
    scanf("%d%d" , &n , &m);
    for(int i = 1 ; i <= n  ; ++i)  scanf("%d" , &a[i]);   
    build(1 , 1 , n);
    while(m--){
        int op , l , r;
        scanf("%d%d%d" , &op , &l , &r);
        if(op & 1){
            int k;
            scanf("%d" , &k);
            update(1 , 1 , n , l , r , k);
        }
        else{
            ll ans = query(1 , 1 , n , l , r);
            printf("%lld\n" , ans);
        }
    }
    return 0;
}