记录编号	324270	评测结果	AAAAAAAAAA
题目名称	[AHOI2009] 行星序列	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.576 s
提交时间	2016-10-17 21:29:29	内存使用	9.45 MiB

#include<cstdio>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("seqb.in","r",stdin);freopen("seqb.out","w",stdout);chul();Cu;
using namespace std;
const int maxn=100010;
long long n,p;
long long tree[maxn<<2],mul[maxn<<2],add[maxn<<2],s,t,c;
void update(int rt,int l,int r,int mid){
    if(l==r)return;
	//printf("pushdown(%d) l=%d r=%d mid=%d\n",rt,l,r,mid);
    int t=rt<<1;
    mul[t]=(mul[t]*mul[rt])%p;
    mul[t|1]=(mul[t|1]*mul[rt])%p;
    add[t]=(add[t]*mul[rt]+add[rt])%p;
    add[t|1]=(add[t|1]*mul[rt]+add[rt])%p;
    tree[t]=(tree[t]*mul[rt]+add[rt]*(mid-l+1))%p;
    tree[t|1]=(tree[t|1]*mul[rt]+add[rt]*(r-mid))%p;
    mul[rt]=1;add[rt]=0;
}
void build(int rt,int l,int r){
	if(l==r){
		scanf("%lld",&tree[rt]);
		//printf("build(%d,%d) rt=%d\n",l,r,rt);
		//printf("sm[%d]=%d\n",rt,tree[rt]);
		tree[rt]%=p;
		add[rt]=0;
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%p;
	mul[rt]=1;
	//printf("build(%d,%d) rt=%d\n",l,r,rt);
	//printf("sm[%d]=%d\n",rt,tree[rt]);
}
void multi(int rt,int l,int r){
	if(s<=l&&t>=r){
		tree[rt]=(tree[rt]*c)%p;
		mul[rt]=(mul[rt]*c)%p;
		add[rt]=(add[rt]*c)%p;
		return;
	}
	int mid=(l+r)>>1;
	update(rt,l,r,mid);
	if(s<=mid)multi(rt<<1,l,mid);
	if(t>mid)multi(rt<<1|1,mid+1,r);
	tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%p;
}
void multi(){
	scanf("%lld%lld%lld",&s,&t,&c);
	multi(1,1,n);
}
void adds(int rt,int l,int r){
	if(s<=l&&t>=r){
		tree[rt]=(tree[rt]+(r-l+1)*c)%p;
		add[rt]=(add[rt]+c)%p;
		return;
	}
	int mid=(l+r)>>1;
	update(rt,l,r,mid);
	if(s<=mid)adds(rt<<1,l,mid);
	if(t>mid)adds(rt<<1|1,mid+1,r);
	tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%p;
}		
void adds(){
	scanf("%lld%lld%lld",&s,&t,&c);
	adds(1,1,n);
}
long long asks(int rt,int l,int r){
	//printf("query(%d,%d) sm[rt=%d]=%d\n",l,r,rt,tree[rt]);
	if(s<=l&&t>=r){
		return tree[rt];
	}
	int mid=(l+r)>>1;
	update(rt,l,r,mid);
	if(t<=mid)return asks(rt<<1,l,mid)%p;
	else if(s>mid)return asks(rt<<1|1,mid+1,r)%p;
	else return ((asks(rt<<1,l,mid)+asks(rt<<1|1,mid+1,r))%p);
	/*long long tmp=0ll;
	if(s<=mid)tmp=(tmp+asks(rt<<1,l,mid))%p;
	if(t>mid)tmp=(tmp+asks(rt<<1|1,mid+1,r))%p;
	return tmp;*/
}
void asks(){
	scanf("%lld%lld",&s,&t);
	printf("%lld\n",asks(1,1,n));
}
void chul(){
	long long m;
	scanf("%lld%lld",&n,&p);
	build(1,1,n);
	scanf("%lld",&m);
	long long k;
	for(int i=0;i<m;i++){
		scanf("%lld",&k);
		if(k==1){
			multi();
		}
		else if(k==2){
			adds();
		}
		else asks();
	}
}   
int main(){
	Begin;
}