思路

只要记录线段树所有区间的一个左端点的值这个题就可以做完..
我们可以假设这个左端点是,对于每次修改操作,我们只要知道左端点的值,我们这个区间修改的值就会变得已知,就可以更新,子区间的值也可以更新.
总之还是线段树不熟练~.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
struct Tree{
    ll l,r,sum,lazy;
}tr[N<<2];
int a[N];
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}

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

void update(int u,int l,int r,int val)
{
    if(l>tr[u].r||r<tr[u].l)    return;
    if(l<=tr[u].l&&tr[u].r<=r)
    {
        tr[u].lazy=(tr[u].l-l+val);
        tr[u].sum=(2ll*tr[u].lazy+tr[u].r-tr[u].l)*(tr[u].r-tr[u].l+1)/2ll;
        return;
    }
    pushdown(u);
    update(u<<1,l,r,val);
    update(u<<1|1,l,r,val);
    pushup(u);
}

ll ask(int u,int l,int r)
{
    if(l>tr[u].r||r<tr[u].l)    return 0;
    if(l<=tr[u].l&&tr[u].r<=r)  return tr[u].sum;
    pushdown(u);
    return ask(u<<1,l,r)+ask(u<<1|1,l,r);
}

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

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