记录编号	57331	评测结果	AAAAAAAAAA
题目名称	[AHOI2009] 行星序列	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.960 s
提交时间	2013-04-09 15:31:15	内存使用	8.71 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iomanip>
using namespace std;
long long MOD;
long long d[100001]={0};//每个点的值
int n;
int tot=0;
class SEGMENT{
public:
	int l,r;//区间
	int lchild,rchild;//两个子节点的静态指针
	long long s;//区间和
	long long inc,mul;//附加的,没有往下加的标记
	void change(long long c,long long m);
	void build(int left,int right);
}tree[200001];
#define now tree[root]
void SEGMENT::build(int left,int right){
	l=left,r=right,inc=0,mul=1;
	if(left<right){
		int mid=(left+right)>>1;
		lchild=++tot;
		tree[tot].build(left,mid);
		rchild=++tot;
		tree[tot].build(mid+1,right);
		s=(tree[lchild].s+tree[rchild].s)%MOD;
	}
	else{
		s=d[left]%MOD;
		lchild=rchild=-1;
	}
}
void SEGMENT::change(long long c,long long m){//乘m加c
	s*=m,s%=MOD;
	s+=(r-l+1)*c,s%=MOD;
	mul*=m,mul%=MOD;
	inc*=m,inc%=MOD;
	inc+=c,inc%=MOD;
}
void add(int root,int x,int y,long long c,long long m,long long pc,long long pm){
	if(root==-1) return;
	now.change(pc,pm);
	if(now.r<x||now.l>y) return;
	if(x<=now.l&&now.r<=y){//包含这个节点
		now.change(c,m);
		return;
	}
	else{
		add(now.lchild,x,y,c,m,now.inc,now.mul);
		add(now.rchild,x,y,c,m,now.inc,now.mul);
		now.inc=0,now.mul=1;
		now.s=(tree[now.lchild].s+tree[now.rchild].s)%MOD;
	}
}
long long getsum(int root,int x,int y,long long pc,long long pm){
	if(root==-1) return 0;
	now.change(pc,pm);
	if(now.r<x||now.l>y) return 0;
	if(x<=now.l&&now.r<=y){
		return now.s;
	}
	else{
		long long x1,x2;
		x1=getsum(now.lchild,x,y,now.inc,now.mul);
		x2=getsum(now.rchild,x,y,now.inc,now.mul);
		now.inc=0,now.mul=1;
		now.s=(tree[now.lchild].s+tree[now.rchild].s)%MOD;
		return (x1+x2)%MOD;
	}
}
int main(){
	freopen("seqb.in","r",stdin);
	freopen("seqb.out","w",stdout);
	cin>>n>>MOD;
	for(int i=1;i<=n;i++) cin>>d[i],d[i]%=MOD;
	tree[tot].build(1,n);
	int m;
	scanf("%d",&m);
	int temp;
	long long k;
	int lnow,rnow;
	for(int i=0;i<m;i++){
		scanf("%d",&temp);
		if(temp==1){
			scanf("%d%d",&lnow,&rnow);
			cin>>k;
			add(0,lnow,rnow,0,k%MOD,0,1);
		}
		else if(temp==2){
			scanf("%d%d",&lnow,&rnow);
			cin>>k;
			add(0,lnow,rnow,k%MOD,1,0,1);
		}
		else{
			scanf("%d%d",&lnow,&rnow);
			cout<<getsum(0,lnow,rnow,0,1)<<endl;
		}
	}
	return 0;
}