区区区间

做法：线段树

思路：

• 看到区间修改区间查询联想到线段树
• 区间内加上一个首项为k公差为1的等差数列
  在pushdown操作可以在左子树的lazy为当前结点的lazy，右子树的lazy为当前结点的lazy加上左子树的长度
  sum利用等差数列求和公式

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=200005;

int n,m;
ll a[N];
struct node{
    int l,r;
    ll lazy,v;
}tree[N<<2];

void pushup(int u){
    tree[u].v=tree[u<<1].v+tree[u<<1|1].v;
}

void pushdown(int u){
    if(tree[u].lazy){
        tree[u<<1].lazy=tree[u].lazy;
        tree[u<<1].v=(tree[u<<1].lazy+tree[u<<1].lazy+tree[u<<1].r-tree[u<<1].l)*(tree[u<<1].r-tree[u<<1].l+1)/2;
        tree[u<<1|1].lazy=tree[u].lazy+(tree[u<<1].r-tree[u<<1].l+1);
        tree[u<<1|1].v=(tree[u<<1|1].lazy+tree[u<<1|1].lazy+tree[u<<1|1].r-tree[u<<1|1].l)*(tree[u<<1|1].r-tree[u<<1|1].l+1)/2;
        tree[u].lazy=0;
    }
}

void build(int u,int l,int r){
    tree[u].l=l,tree[u].r=r;
    if(l==r){
        tree[u].v=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int v){
    if(l<=tree[u].l&&tree[u].r<=r){
        tree[u].lazy=tree[u].l-l+v;
        tree[u].v=(tree[u].lazy+tree[u].lazy+tree[u].r-tree[u].l)*(tree[u].r-tree[u].l+1)/2;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) modify(u<<1,l,r,v);
    else if(l>mid) modify(u<<1|1,l,r,v);
    else modify(u<<1,l,r,v),modify(u<<1|1,l,r,v);
    pushup(u);
}

ll query(int u,int l,int r){
    if(l<=tree[u].l&&tree[u].r<=r) return tree[u].v;
    pushdown(u);
    ll res=0;
    int mid=(tree[u].l+tree[u].r)>>1;
    if(r<=mid) res+=query(u<<1,l,r);
    else if(l>mid) res+=query(u<<1|1,l,r);
    else res+=query(u<<1,l,r)+query(u<<1|1,l,r);
    return res;
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--){
        int op;cin>>op;
        if(op==1){
            int l,r,k;cin>>l>>r>>k;
            modify(1,l,r,k);
        }
        else{
            int l,r;cin>>l>>r;
            cout<<query(1,l,r)<<"\n";
        }
    }
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}