题解 | #区间 (interval)#

看完题第一反应线段树。

然后 copy 了一个朴素板子过来发现数据范围 $10^{6}10^6$，怀疑出题人可能卡常。

然后就想到了 zkw 的非递归式写法，常数很小。

复制完了模板之后反应过来好像可以差分数组 $O(n)O(n)$ 做（大雾）

线段树做法不讲了，来说说差分数组：

• 设 $d[i]=a[i]-a[i-1]d[i]=a[i]-a[i-1]$
• 那么一次修改就可以等效成两个点的加减法
• 一次查询就直接把差分数组做一遍前缀和，就可以算出来原数组了

#include<cmath>
#include<cstdio>
#define int long long
#define ll long long
inline int in();
inline void wr(ll);
const int N=(int)1e6+5;
ll k=1,tree[N<<2],Add[N<<2];
inline ll search(int,int);
inline void rebuild(int,int,int);
signed main(signed argc,char**argv){
	int n=in(),m=in();
	while(k<=n+1)k<<=1;
	for(int i=k+1;i<=k+n;++i)
		tree[i]=in();
	for(int i=k-1;i>=1;--i)
		tree[i]=tree[i<<1]+tree[i<<1|1];
	for(int i=1;i<=m;++i){
		int tp=in(),x=in(),y=in();
		if(tp==1){
			int z=in();
			rebuild(x,y,-z);
		}
		else{
			int z=in();
			rebuild(x,y,z);
		}
	}
    int l=in(),r=in();
    wr(search(l,r)),putchar('\n');
}
inline ll search(int l,int r){
	l+=k-1,r+=k+1;
	int nL=0,nR=0,nSum=1;
	ll ans=0;
	while(l^r^1){
		if(Add[l])ans+=Add[l]*nL;
		if(Add[r])ans+=Add[r]*nR;
		if(~l&1)
			ans+=tree[l^1],
			nL+=nSum;
		if(r&1)
			ans+=tree[r^1],
			nR+=nSum;
		l>>=1,r>>=1,nSum<<=1;
	}
	while(l){
		ans+=Add[l]*nL+Add[r]*nR;
		l>>=1,r>>=1;
	}
	return ans;
}
inline void rebuild(int l,int r,int x){
	l+=k-1,r+=k+1;
	int nL=0,nR=0,nSum=1;
	while(l^r^1){
		tree[l]+=x*nL,tree[r]+=x*nR;
		if(~l&1)
			Add[l^1]+=x,
			tree[l^1]+=x*nSum,
			nL+=nSum;
		if(r&1)
			Add[r^1]+=x,
			tree[r^1]+=x*nSum,
			nR+=nSum;
		l>>=1,r>>=1,nSum<<=1;
	}
	while(l){
		tree[l]+=x*nL,tree[r]+=x*nR;
		l>>=1,r>>=1;
	}
}
inline int in(){
	char c=getchar();
	int x=0,f=1;
	for(;c<'0'||c>'9';c=getchar())
		if(c=='-')f=-1;
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c&15);
	return x*f;
}
inline void wr(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x/10)wr(x/10);
	putchar(x%10+'0');
}