记录编号	433997	评测结果	AAAAAAAAAA
题目名称	1272.[AHOI2009] 行星序列	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	2.444 s
提交时间	2017-08-06 20:18:08	内存使用	19.39 MiB

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#define ll long long
#define maxn 500005
using namespace std;
ll ls[maxn],rs[maxn],sum[maxn],lazys[maxn],lazyt[maxn],p;
ll ai,n,m,le,ri,opt;
void buildtree(ll l,ll r,ll rt){
     ls[rt]=l; 
	 rs[rt]=r; 
	 sum[rt]=0;
	 lazys[rt]=0; 
	 lazyt[rt]=1;	
     if(l==r) return ;
     int mid=(l+r)>>1;
     buildtree(l,mid,rt*2);
     buildtree(mid+1,r,rt*2+1);
}
void pushdown(ll rt){
	 if(lazys[rt]==0&&lazyt[rt]==1) return ;
	 lazyt[rt*2]=(lazyt[rt*2]*lazyt[rt])%p;
     lazys[rt*2]=(lazys[rt*2]*lazyt[rt]+lazys[rt])%p;
     sum[rt*2]=(sum[rt*2]*lazyt[rt]+(rs[rt*2]-ls[rt*2]+1)*lazys[rt])%p;
     lazyt[rt*2+1]=(lazyt[rt*2+1]*lazyt[rt])%p;
     lazys[rt*2+1]=(lazys[rt*2+1]*lazyt[rt]+lazys[rt])%p;
     sum[rt*2+1]=(sum[rt*2+1]*lazyt[rt]+(rs[rt*2+1]-ls[rt*2+1]+1)*lazys[rt])%p;
     lazys[rt]=0;
     lazyt[rt]=1;
}
void update(ll rt,ll l,ll r,ll mul,ll add){
	 if(ls[rt]>=l&&rs[rt]<=r){
	 	lazyt[rt]=(lazyt[rt]*mul)%p;
	 	lazys[rt]=(lazys[rt]*mul+add)%p;
	 	sum[rt]=(sum[rt]*mul+(rs[rt]-ls[rt]+1)*add)%p;
	    return;
	 }
	 pushdown(rt);
	 ll mid=(ls[rt]+rs[rt])>>1;
	 if(r<=mid) update(rt*2,l,r,mul,add);
	 else if(l>mid) update(rt*2+1,l,r,mul,add);
          else update(rt*2,l,mid,mul,add),update(rt*2+1,mid+1,r,mul,add);
	 sum[rt]=(sum[rt*2]+sum[rt*2+1])%p; 
}
ll query(ll rt,ll l,ll r){
	if(ls[rt]>=l&&rs[rt]<=r) return sum[rt];
	pushdown(rt);
	int mid=(ls[rt]+rs[rt])>>1;
	if(r<=mid) return query(rt*2,l,r);
	else if(l>mid) return query(rt*2+1,l,r);
	     else return (query(rt*2,l,mid)+query(rt*2+1,mid+1,r))%p;
}		
int main(){
	freopen("seqb.in","r",stdin);
	freopen("seqb.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	buildtree(1,n,1);	
	for(int i=1;i<=n;i++){
	    scanf("%lld",&ai);
	    update(1,i,i,1,ai);
	}scanf("%lld",&m);
	while(m--){
          scanf("%lld%lld%lld",&opt,&le,&ri);
          if(opt==1){scanf("%lld",&ai);update(1,le,ri,ai,0);}
          if(opt==2){scanf("%lld",&ai);update(1,le,ri,1,ai);}
          if(opt==3) printf("%lld\n",query(1,le,ri));
    }
}