题目还是没法粘贴……
一道蛮不错的题。
老年选手困了30min后才想要推式子实在是太懒了……
我们可以对每次更新列表看成系数*x即可。
举例：第i次有列表(l,r,x)，则第j次求和时答案*(j-i)即可。
但是系数不统一很难受，于是得到：(i-k)*x=(i-1)*a，求a=x+(1-k)*x/(i-1)，则(i-1)*a=(i-1)*x+(1-k)*x
于是我们用线段树多维护一个(1-k)*x就行了。
注意一下线段树常数问题。
#include<algorithm> #include<iostream> #include<cstring> #include<cctype> #include<cstdio> #include<queue> #include<cmath> using namespace std; typedef long long ll; const int N=1e5+5; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } ll b[N],tr[N*4],lz[N*4],t[N*4],lazy[N*4]; inline void push(int a,int l,int r){ int mid=(l+r)>>1; lz[a<<1]+=lz[a];lz[a<<1|1]+=lz[a]; tr[a<<1]+=lz[a]*(mid-l+1);tr[a<<1|1]+=lz[a]*(r-mid); lz[a]=0; lazy[a<<1]+=lazy[a];lazy[a<<1|1]+=lazy[a]; t[a<<1]+=lazy[a]*(mid-l+1);t[a<<1|1]+=lazy[a]*(r-mid); lazy[a]=0; } void mdy(int a,int l,int r,int l1,int r1,ll w,bool on){ if(r<l1||r1<l)return; if(l1<=l&&r<=r1){ if(!on)lz[a]+=w,tr[a]+=w*(r-l+1); else lazy[a]+=w,t[a]+=w*(r-l+1); return; } push(a,l,r); int mid=(l+r)>>1; mdy(a<<1,l,mid,l1,r1,w,on);mdy(a<<1|1,mid+1,r,l1,r1,w,on); tr[a]=tr[a<<1]+tr[a<<1|1]; t[a]=t[a<<1]+t[a<<1|1]; } ll qry(int a,int l,int r,int l1,int r1,ll k){ if(r<l1||r1<l)return 0; if(l1<=l&&r<=r1)return k*tr[a]+t[a]; push(a,l,r); int mid=(l+r)>>1; return qry(a<<1,l,mid,l1,r1,k)+qry(a<<1|1,mid+1,r,l1,r1,k); } int main(){ int n=read(); for(int i=1;i<=n;i++)b[i]=b[i-1]+read(); int m=read(); for(int i=1;i<=m;i++){ int d=read(); if(d==1){ int l=read(),r=read(),x=read(); mdy(1,1,n,l,r,x,0);mdy(1,1,n,l,r,(1-i)*x,1); }else{ int l=read(),r=read(); printf("%lld ",b[r]-b[l-1]+qry(1,1,n,l,r,i-1)); } } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +
+++++++++++++++++++++++++++++++++++++++++++