【题解】区区区间

线段数可以做。线段树是什么？戳

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define MAXN 200001
#define lson now<<1
#define rson now<<1|1
#define int long long

inline void read(int &T) {
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    T=f?-x:x;
}

int n,q;
struct node {
    int l,r,w,lazy;
}tree[MAXN<<2];

void build(int l,int r,int now) {
    tree[now].l=l;tree[now].r=r;tree[now].lazy=-1525461647;
    if(tree[now].l==tree[now].r) {read(tree[now].w);return;}
    int mid=(tree[now].l+tree[now].r)>>1;
    build(l,mid,lson),build(mid+1,r,rson);
    tree[now].w=tree[lson].w+tree[rson].w;
}

void pushdown(int now) {
    tree[lson].lazy=tree[now].lazy;tree[rson].lazy=tree[now].lazy+tree[lson].r-tree[lson].l+1;
    tree[lson].w=((tree[lson].r-tree[lson].l+1)*(tree[now].lazy+tree[rson].lazy-1))/2;
    tree[rson].w=((tree[rson].r-tree[rson].l+1)*(tree[rson].lazy+tree[rson].lazy+tree[rson].r-tree[rson].l))/2;

    tree[now].lazy=-1525461647;
}

void update(int x,int y,int k,int now) {
    if(tree[now].l>=x&&tree[now].r<=y) {
        tree[now].lazy=k+tree[now].l-x;
        tree[now].w=((tree[now].r-tree[now].l+1)*(tree[now].lazy+k-x+tree[now].r))/2;return;
    }
    if(tree[now].lazy!=-1525461647) pushdown(now);
    int mid=(tree[now].l+tree[now].r)>>1;
    if(x<=mid) update(x,y,k,lson);
    if(y>mid) update(x,y,k,rson);
    tree[now].w=tree[lson].w+tree[rson].w;
}

int query(int x,int y,int now) {
    if(tree[now].l>=x&&tree[now].r<=y) return tree[now].w;
    if(tree[now].lazy!=-1525461647) pushdown(now);
    int mid=(tree[now].l+tree[now].r)>>1,ans=0;
    if(x<=mid) ans+=query(x,y,lson);
    if(y>mid) ans+=query(x,y,rson);
    return ans;
}

signed main() {
    read(n),read(q);
    build(1,n,1);
    int opt,x,y,k;
    for(int i=1;i<=q;++i) {
        read(opt),read(x),read(y);
        if(opt==1) read(k),update(x,y,k,1);
        if(opt==2) printf("%lld\n",query(x,y,1));
    }
    return 0;
}