NC200195 区区区间

线段树区间覆盖问题，主要难点在于lazy标签要怎么用，我们可以定义lazy标签标示对于根节点now来说，他的整个区间也就是[now.l,now.r]是以now.lazy为首项的等差数列，以及作为区间覆盖的标准的话，那这道题和普通的区间覆盖就没有区别了，当然还有别的做法。

#include<iostream>
using namespace std;
const int N=2e5+10;
typedef long long ll;
struct node
{
    int l,r;
    ll v,lazy;
}tree[4*N];
int n,m;
ll getnum(ll x,ll len)
{
    ll ans=0;
    ans=(x+x+len-1)*len/2;
    return ans;
}
void build(int l,int r,int now)
{
    tree[now].l=l;
    tree[now].r=r;
    int mid=(l+r)/2;
    if(l==r){
        cin>>tree[now].v;return;
    }
    else{
        build(l,mid,now*2);
        build(mid+1,r,now*2+1);
    }
    tree[now].v=tree[now*2].v+tree[now*2+1].v;
    return;
}
void pushdown(int now)
{
    int mid=(tree[now].l+tree[now].r)/2;
    int num=tree[now].lazy;
    int l=tree[now].l;
    int r=tree[now].r;
    tree[2*now].v=getnum(num,mid-l+1);
    tree[2*now].lazy=num;
    tree[2*now+1].v=getnum(num+mid+1-l,r-mid);
    tree[2*now+1].lazy=num+mid+1-l;
    tree[now].lazy=0;
    return;
}
void update(int num,int l,int r,int now)
{
    // cout<<l<<" "<<r<<endl;
    int mid=(tree[now].l+tree[now].r)/2;
    if(tree[now].l==l&&tree[now].r==r)
    {
        tree[now].v=ll(num+num+r-l)*(r-l+1)/2;
        tree[now].lazy=num;
        return;
    }
    if(tree[now].lazy!=0)pushdown(now);
    if(r<=mid)update(num,l,r,2*now);
    else if(l>=mid+1)update(num,l,r,2*now+1);
    else
    {
        update(num,l,mid,2*now);
        update(num+mid+1-l,mid+1,r,2*now+1);
    }
    tree[now].v=tree[2*now].v+tree[2*now+1].v;
    return;
}
ll getsum(int l,int r,int now)
{
    int mid=(tree[now].l+tree[now].r)/2;
    if(tree[now].l==l&&tree[now].r==r)return tree[now].v;
    if(tree[now].lazy!=0)pushdown(now);
    ll ans=0;
    if(r<=mid)ans+=getsum(l,r,2*now);
    else if(l>=mid+1)ans+=getsum(l,r,2*now+1);
    else ans+=getsum(l,mid,2*now)+getsum(mid+1,r,2*now+1);
    return ans;
}
int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    build(1,n,1);//建树
    int op,l,r,k;
    while(m--)
    {
        cin>>op;
        if(op==1)
        {
            cin>>l>>r>>k;
            update(k,l,r,1);
        }
        else
        {
            cin>>l>>r;
            cout<<getsum(l,r,1)<<endl;
        }
    }
}