区区区间

题解：

线段树，不过这里线段树区间维护要换一种方法。
我们发现这个等差数列的等差为1。对于修改一段区间如果我们知道首项值，那么我们便可以在的时间复杂度计算出这段区间的大小。
又可以知道，对于线段树每一个结点，代表一段区间，那么我们我们用lazy数组保存这一段区间的首项，那么我们便可以在O（1）的时间复杂度内算出这一段区间的值。

代码：

#pragma GCC optimize(3 , "Ofast" , "inline")

#include<bits/stdc++.h>
//#define ll long long
using namespace std;
#define endl '\n'
#define int long long
const int maxn=1e6+10;
const int mod=1e9+7;

int tree[maxn],a[maxn];
int lazy[maxn];

void push_up(int node){
    tree[node]=tree[node*2+1]+tree[node*2];
}

void build(int node,int l,int r){
    if(l==r){
        tree[node]=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    push_up(node);
}

int cal(int x,int len){
    return (2*x+len-1)*len/2;
}

void push_down(int node,int start,int ends){
    if(lazy[node]){
        int mid=(start+ends)/2;
        lazy[node*2]=lazy[node];
        lazy[node*2+1]=lazy[node]+mid-start+1;
        tree[node*2]=cal(lazy[node*2],mid-start+1);
        tree[node*2+1]=cal(lazy[node*2+1],ends-mid);
        lazy[node]=0;
    }
}

void update(int node,int start,int ends,int l,int r,int val){
    if(start>=l&&ends<=r){
        lazy[node]=val+start-l;
        tree[node]=cal(val+start-l,ends-start+1);
        //cout<<"debug  "<<start<<" "<<ends<<" "<<lazy[node]<<" "<<tree[node]<<endl;
        return ;
    }
    push_down(node,start,ends);
    int mid=(start+ends)/2;
    if(l<=mid) update(node*2,start,mid,l,r,val);
    if(mid<r) update(node*2+1,mid+1,ends,l,r,val);
    push_up(node);
}

int query(int node,int start,int ends,int l,int r){
    if(start>=l&&ends<=r){
        return tree[node];
    }
    push_down(node,start,ends);
    int mid=(start+ends)/2;
    int res=0;
    if(l<=mid) res+=query(node*2,start,mid,l,r);
    if(mid<r) res+=query(node*2+1,mid+1,ends,l,r);
    return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    //cout<<query(1,1,n,1,5)<<endl;;
    for(int i=0;i<m;i++){
        int opt;
        cin>>opt;
        if(opt==1){
            int x,y,k;
            cin>>x>>y>>k;
            update(1,1,n,x,y,k);
        }
        else{
            int x,y;
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<endl;;
        }
        //cout<<query(1,1,n,1,5)<<endl;;
    }

}