C++14(g++5.4) 解法, 执行用时: 285ms, 内存消耗: 8412K, 提交时间: 2019-06-15 11:23:35

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll c1[N*4],c2[N*4],a[N],lazy[N*4];
int n,m;
void build(int id,int l,int r)
{
	if(l==r)
	{
		ll x;
		scanf("%lld",&x);
		c1[id]=x;
		c2[id]=x*x;
		return ;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	c1[id]=c1[id<<1]+c1[id<<1|1];
	c2[id]=c2[id<<1]+c2[id<<1|1];
}
void pushdown(int id,int l,int r)
{
	if(lazy[id])
	{
		int mid=l+r>>1;
		int l1=mid-l+1;
		int l2=r-mid;
		c2[id<<1]+=l1*lazy[id]*lazy[id]+2*c1[id<<1]*lazy[id];
		c2[id<<1|1]+=l2*lazy[id]*lazy[id]+2*c1[id<<1|1]*lazy[id];
		
		c1[id<<1]+=l1*lazy[id];
		c1[id<<1|1]+=l2*lazy[id];
		
		lazy[id<<1]+=lazy[id];
		lazy[id<<1|1]+=lazy[id];
		lazy[id]=0;
	}
}
void up(int id,int l,int r,int ql,int qr,ll val)
{
	if(ql<=l&&r<=qr)
	{
		int len=r-l+1;
		c2[id]+=val*val*len+2*c1[id]*val;
		c1[id]+=val*len;
		lazy[id]+=val;
		return ;
	}
	pushdown(id,l,r);
	int mid=l+r>>1;
	if(ql<=mid) up(id<<1,l,mid,ql,qr,val);
	if(qr>mid) up(id<<1|1,mid+1,r,ql,qr,val);
	c1[id]=c1[id<<1]+c1[id<<1|1];
	c2[id]=c2[id<<1]+c2[id<<1|1];
}

ll qu(int id,int l,int r,int ql,int qr,int op)
{
	if(ql<=l&&r<=qr) 
	{
		if(op==1)	return c1[id];
		else return c2[id];
	}
	pushdown(id,l,r);
	ll ans=0;
	int mid=l+r>>1;
	if(ql<=mid) ans+=qu(id<<1,l,mid,ql,qr,op);
	if(qr>mid) ans+=qu(id<<1|1,mid+1,r,ql,qr,op);
	return ans;
}

int main()
{
	cin>>n>>m;
	build(1,1,n);
	for(int i=1;i<=m;++i)
	{
		int ty,l,r;
		ll val;
		scanf("%d%d%d",&ty,&l,&r);
		if(ty==1) 
		{
			scanf("%lld",&val);
			up(1,1,n,l,r,val);
		}
		else
		{
			ll nu1=qu(1,1,n,l,r,1);
			ll nu2=qu(1,1,n,l,r,2);
			printf("%lld\n",(nu1*nu1-nu2)/2);
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 114ms, 内存消耗: 7544K, 提交时间: 2020-02-01 15:08:10

#include<bits/stdc++.h>
using namespace std;

long long a[100005],S1[400005],S2[400005];
long long s1,s2,y,T[400005]={0};
void build(int L,int R,int x)
{
	if(L==R)
	{
		S1[x]=a[L],S2[x]=a[L]*a[L];
		return;
	}
	int M=(L+R)>>1;
	build(L,M,2*x);
	build(M+1,R,2*x+1);
	S1[x]=S1[2*x]+S1[2*x+1];
	S2[x]=S2[2*x]+S2[2*x+1];
}
void down(int L,int R,int x)
{
	if(!T[x])return;
	int M=(L+R)>>1;
	T[2*x]+=T[x],T[2*x+1]+=T[x];
	S2[2*x]+=2*S1[2*x]*T[x]+T[x]*T[x]*(M-L+1);
	S2[2*x+1]+=2*S1[2*x+1]*T[x]+T[x]*T[x]*(R-M);
	S1[2*x]+=(M-L+1)*T[x];
	S1[2*x+1]+=(R-M)*T[x];
	T[x]=0;
}
void add(int L,int R,int l,int r,int x)
{
	if(l<=L&&R<=r)
	{
		T[x]+=y;
		S2[x]+=2*S1[x]*y+y*y*(R-L+1);
		S1[x]+=(R-L+1)*y;
		return;
	}
	down(L,R,x);
	int M=(L+R)>>1;
	if(M>=l)add(L,M,l,r,2*x);
	if(M<r)add(M+1,R,l,r,2*x+1);
	S1[x]=S1[2*x]+S1[2*x+1];
	S2[x]=S2[2*x]+S2[2*x+1];
}
void search(int L,int R,int l,int r,int x)
{
	if(l<=L&&R<=r)
	{
		s1+=S1[x],s2+=S2[x];
		return;
	}
	down(L,R,x);
	int M=(L+R)>>1;
	if(M>=l)search(L,M,l,r,2*x);
	if(M<r)search(M+1,R,l,r,2*x+1);
}
int main()
{
	int i,n,Q,f,l,r;
	scanf("%d%d",&n,&Q);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,n,1);
	while(Q--)
	{
		scanf("%d%d%d",&f,&l,&r);
		if(f==1)scanf("%lld",&y),add(1,n,l,r,1);
		else
		{
			s1=s2=0,search(1,n,l,r,1);
			printf("%lld\n",(s1*s1-s2)/2);
		}
	}
	return 0;
}