【代码】
#include#include #include #include #include #include #include using namespace std;#define f(i,n) for(int i=1;i<=(n);i++)#define ll long long#define INF 1<<30#define N 100010int read(){ int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while( isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f;}int a[N];ll maxn[3*N],sum[3*N],minn[3*N],sumf[3*N],tag[3*N];int n,q,z;//向上传递 void pushup(int o,int l,int r){ int lo=2*o,ro=2*o+1,m=(l+r)>>1; sum[o]=sum[lo]+sum[ro]; maxn[o]=max(maxn[lo],maxn[ro]); minn[o]=min(minn[lo],minn[ro]); sumf[o]=sumf[lo]+sumf[ro];}//定义线段树 void dingyi(int o,int l,int r){ if(l==r) { sum[o]=maxn[o]=minn[o]=a[l]; sumf[o]=a[l]*a[l]; return; } int lo=2*o,ro=2*o+1,m=(l+r)>>1; dingyi(lo,l,m); dingyi(ro,m+1,r); pushup(o,l,r);}//向下传递tag void pushdown(int o,int l,int r){ if(l==r)return; int lo=2*o,ro=2*o+1,m=(l+r)>>1; if(tag[o]) { tag[lo]+=tag[o]; tag[ro]+=tag[o]; sumf[lo]+=(ll)(m-l+1)*tag[o]*tag[o]+(ll)2*tag[o]*sum[lo]; sumf[ro]+=(ll)(r-m)*tag[o]*tag[o]+(ll)2*tag[o]*sum[ro]; sum[lo]+=(ll)(m-l+1)*tag[o]; sum[ro]+=(ll)(r-m)*tag[o]; maxn[lo]+=tag[o]; maxn[ro]+=tag[o]; minn[lo]+=tag[o]; minn[ro]+=tag[o]; } tag[o]=0;}//区间加 int addl,addr,addi;void add(int o,int l,int r){ if(l>=addl&&r<=addr) { sumf[o]+=(ll)(r-l+1)*addi*addi+2ll*addi*sum[o]; sum[o]+=(ll)(r-l+1)*addi; maxn[o]+=addi; minn[o]+=addi; tag[o]+=addi; return; } pushdown(o,l,r); int lo=2*o,ro=2*o+1,m=(l+r)>>1; if(addl<=m)add(lo,l,m); if(addr>m)add(ro,m+1,r); pushup(o,l,r);}//区间查询 ll qsum=0,qsumf=0;int ql,qr;void query(int o,int l,int r){ if(l>=ql&&r<=qr) { qsum+=sum[o]; qsumf+=sumf[o]; return; } int lo=2*o,ro=2*o+1,m=(l+r)>>1; pushdown(o,l,r); if(ql<=m)query(lo,l,m); if(qr>m)query(ro,m+1,r); pushup(o,l,r);}int main(){ n=read(); q=read(); f(i,n)a[i]=read(); dingyi(1,1,n); f(i,q) { z=read(); if(z==1) { addl=read(); addr=read(); scanf("%lld",&addi); if(addi==0)continue; add(1,1,n); } if(z==2) { ql=read(); qr=read(); qsum=0; qsumf=0; query(1,1,n); } }}