数据结构：线段树——求区间N次方和模板

点击查看折叠代码块

/*
将某区间每一个数乘上 x

将某区间每一个数加上 x

求出某区间每一个数的和

假设区间一次方和为Sum1
现在要求区间二次方和和三次方...n次方和

设区间一次方和Sum1 = a+b+c+d+...
则区间二次方和为Sum2 = a^2+b^2+c^2+d^2+...
区间每个值增加x后：Sum2=(a+x)^2+(b+x)^2+(c+x)^2+... = 
(a^2+b^2+c^2+...) + (2*(a+b+c...)*x) + 2*n*(x)^2        
=Sum2 + 2*Sum1*x + 2*n*x*x           //n为区间长度

类似的三次方，n次方也可以展开后求解
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define N 100005
#define lson l,m,i<<1
#define rson m+1,r,i<<1|1
#define LL long long
LL sum[N<<2];
LL lazyadd[N<<2];
LL lazymul[N<<2];

int n,m,p;

void pushup(int i){
	sum[i]=(sum[i<<1] + sum[i<<1|1]) % p;
} 

void pushdown(int l,int r,int i){
	if(lazyadd[i]==0 && lazymul[i]==1) return;
	LL t1=lazyadd[i],t2=lazymul[i];
	lazyadd[i<<1]=(lazyadd[i<<1] * t2 + t1) % p;
	lazyadd[i<<1|1]=(lazyadd[i<<1|1] * t2 + t1) % p;
	lazymul[i<<1]=(lazymul[i<<1] * t2) % p;
	lazymul[i<<1|1]=(lazymul[i<<1|1] * t2) % p;
	
	int m=(l+r)>>1;
	sum[i<<1]=(sum[i<<1] * t2 + t1 * (m-l+1) ) % p;
	sum[i<<1|1]=(sum[i<<1|1] * t2 + t1 * (r-m) ) % p;
	lazyadd[i]=0; lazymul[i]=1;
}

void build(int l,int r,int i){
	lazyadd[i]=0;
	lazymul[i]=1;
	if(l==r) {
		scanf("%lld",&sum[i]);
		sum[i]=sum[i] % p;
		return ;
	}
	
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(i);
	sum[i]=sum[i] % p;
}

void add(int L,int R,int v,int l,int r,int i){
	if(L<=l && r<=R){
		lazyadd[i]=(lazyadd[i]+v) % p;
		sum[i]=(sum[i] + v*(r-l+1) ) % p;
		return ;
	}
	
	pushdown(l,r,i);
	int m=(l+r)>>1;
	if(L<=m) add(L,R,v,lson);
	if(R>m) add(L,R,v,rson);
	pushup(i);
}

void mul(int L,int R,int v,int l,int r,int i){
	if(L<=l && r<=R){
		lazymul[i]=(lazymul[i] * v) % p;
		lazyadd[i]=(lazyadd[i] * v) % p;
		sum[i]=(sum[i] * v) % p;
		return ;
	}
	
	pushdown(l,r,i);
	int m=(l+r)>>1;
	if(L<=m) mul(L,R,v,lson);
	if(R>m) mul(L,R,v,rson);
	pushup(i);
}

LL query(int L,int R,int l,int r,int i){
	if(L<=l && r<=R){
		return sum[i];
	}
	
	pushdown(l,r,i);
	int m=(l+r)>>1;
	LL ans=0;
	if(L<=m) ans+=query(L,R,lson);
	if(R>m) ans+=query(L,R,rson);
	return ans % p;
}

int main(){
int ques;
	scanf("%d%d%d",&n,&ques,&p);
	build(1,n,1);
	
	for (int i=0;i<ques;i++){
		int cnt;
		scanf("%d",&cnt);
		if(cnt==1){
			int val,a,b;
			scanf("%d%d%d",&a,&b,&val);
			mul(a,b,val,1,n,1);
		}
		else if(cnt==2){
			int val,a,b;
			scanf("%d%d%d",&a,&b,&val);
			add(a,b,val,1,n,1);
		}
		else if(cnt==3){
			int a,b;
			scanf("%d%d",&a,&b);
			LL ans=query(a,b,1,n,1);
			printf("%lld
",ans%p);
		}
	}
	return 0;
}
/*
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

17
2
*/