线段数可以做。线段树是什么?戳
#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; }