记录编号	451966	评测结果	AAAAAAAAAA
题目名称	[AHOI2009] 行星序列	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	3.286 s
提交时间	2017-09-18 18:45:59	内存使用	10.23 MiB

#include<bits/stdc++.h>
#define ll long long
#define ls o<<1
#define rs o<<1|1
#define mid ((r+l)>>1)
using namespace std;
const int ma=100005;
ll n,p,a[ma],f[ma<<2],add[ma<<2],mul[ma<<2],m;
void build(ll l,ll r,ll o){
	mul[o]=1;
	if(l==r){
		f[o]=a[l];
		f[o]%=p;
		return ;
	}
	build(l,mid,ls);
	build(mid+1,r,rs);
	f[o]=f[ls]+f[rs];
	f[o]%=p;
}
void pushdown(ll l,ll r,ll o){
	mul[ls]*=mul[o];mul[ls]%=p;
	add[ls]*=mul[o];add[ls]%=p;
	add[ls]+=add[o];add[ls]%=p;
	mul[rs]*=mul[o];mul[rs]%=p;
	add[rs]*=mul[o];add[rs]%=p;
	add[rs]+=add[o];add[rs]%=p;
	add[o]=0;mul[o]=1;
}
void update(ll l,ll r,ll o){
	ll tem1=mul[ls]*f[ls]%p+add[ls]*(mid-l+1)%p;
	tem1%=p;
	ll tem2=mul[rs]*f[rs]%p+add[rs]*(r-mid)%p;
	tem2%=p;
	f[o]=tem1+tem2;
	f[o]%=p;
}
void change1(ll l,ll r,ll o,ll L,ll R,ll x){
	if(l>=L&&r<=R){
		mul[o]*=x;add[o]*=x;
		mul[o]%=p;add[o]%=p;
		return ;
	}pushdown(l,r,o);
	if(mid>=L)change1(l,mid,ls,L,R,x);
	if(mid<R)change1(mid+1,r,rs,L,R,x);
	update(l,r,o);
}
void change2(ll l,ll r,ll o,ll L,ll R,ll x){
	if(l>=L&&r<=R){
		add[o]+=x;add[o]%=p;
		return ;
	}pushdown(l,r,o);
	if(mid>=L)change2(l,mid,ls,L,R,x);
	if(mid<R)change2(mid+1,r,rs,L,R,x);
	update(l,r,o);
}
ll q(ll l,ll r,ll o,ll L,ll R){
	ll k=0;
	if(l>=L&&r<=R){
		k+=f[o];
		k*=mul[o];
		k%=p;
		k+=add[o]*(r-l+1);
		k%=p;
		return k;
	}pushdown(l,r,o);
	if(mid>=L)k+=q(l,mid,ls,L,R);
	if(mid<R)k+=q(mid+1,r,rs,L,R);
	update(l,r,o);
	return k%p;
}
int main()
{
	freopen("seqb.in","r",stdin);
	freopen("seqb.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%lld%lld",&n,&p);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,n,1);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		ll x,t,g,c;
		scanf("%lld%lld%lld",&x,&t,&g);
		if(x==1){
			scanf("%lld",&c);
			change1(1,n,1,t,g,c);
		}
		if(x==2){
			scanf("%lld",&c);
			change2(1,n,1,t,g,c);
		}
		if(x==3){
			printf("%lld\n",q(1,n,1,t,g));
		}
	}
	return 0;
}