记录编号	236023	评测结果	AAAAAAAAAA
题目名称	[AHOI2009] 行星序列	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	2.510 s
提交时间	2016-03-12 11:14:05	内存使用	9.45 MiB

#define lson l,m,t
#define rson m+1,r,t|1

#include<cstdio>

using namespace std;

int n,p,m,pd;
long long tree[400010];
int posl,posr,newdata;
long long add[400010],mul[400010];

void Build(int l,int r,int rt)
{
     if(l==r){
         scanf("%lld",&tree[rt]);
         tree[rt]%=p;
         return;
     }
     int m=(l+r)>>1,t=rt<<1;
     Build(lson);
     Build(rson);
     tree[rt]=(tree[t]+tree[t|1])%p;
}

void clear(int l,int r,int rt)
{
    if(l==r)return;
    int m=(l+r)>>1,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]*(m-l+1))%p;
    tree[t|1]=(tree[t|1]*mul[rt]+add[rt]*(r-m))%p;
    mul[rt]=1;add[rt]=0;
}

void plus(int l,int r,int rt)
{
     if(posl<=l&&posr>=r){
         add[rt]=(add[rt]+newdata)%p;
         tree[rt]=(tree[rt]+newdata*(r-l+1))%p;
         return;
     }
     clear(l,r,rt);
     int m=(l+r)>>1,t=rt<<1;
     if(posl<=m)plus(lson);
     if(posr>m)plus(rson);
     tree[rt]=(tree[t]+tree[t|1])%p;
}

void multi(int l,int r,int rt)
{
     if(posl<=l&&posr>=r){
         tree[rt]=(tree[rt]*newdata)%p;
         mul[rt]=(mul[rt]*newdata)%p;
         add[rt]=(add[rt]*newdata)%p;
         return;
     }
     clear(l,r,rt);
     int m=(l+r)>>1,t=rt<<1;
     if(posl<=m)multi(lson);
     if(posr>m)multi(rson);
     tree[rt]=(tree[t]+tree[t|1])%p;
}

long long query(int l,int r,int rt)
{
    if(posl<=l&&posr>=r)
        return tree[rt];
    int m=(l+r)>>1,t=rt<<1;
    long long sum=0;
    clear(l,r,rt);
    if(posl<=m)
        sum=sum+query(lson);
    if(posr>m)
        sum=sum+query(rson);
    return sum%p;
}

int main()
{
    freopen("seqb.in","r",stdin);
    freopen("seqb.out","w",stdout);
    scanf("%d%d",&n,&p);
    Build(1,n,1);
    for(int i=1;i<=4*n;i++)mul[i]=1;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&pd);
        if(pd==1||pd==2){
            scanf("%d%d%d",&posl,&posr,&newdata);
            newdata%=p;
            if(pd==1)multi(1,n,1);
            else plus(1,n,1);
        }
        else{
             scanf("%d%d",&posl,&posr);
             printf("%lld\n",query(1,n,1)%p);
        }
    }
}