菜，所以想用指针写线段树。

然后 T 了（没开O2）。 Record。

然后随便贺了个题解本地对拍，最大数据 Averagetime 稳定在 625ms 左右，题解大概 460ms，（测时用的是 chy-2003 在 github 上的一个对拍代码）。

然后觉得很离谱，下数据本地测了一下。1130ms（但是测试点显示的是 >1.20s）。

有没有人能帮忙康康，是指针写法本身常数大，还是我实现方法常数大。

本地的编译选项是 g++ -std=c++11 -Wall -D LOCAL Main.cpp -o Main。

我的代码（马蜂有些诡异，sum是不包含 tag 的区间和，~ 是 pushdown）：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#ifdef LOCAL
#include<chrono>
#endif
using namespace std;
void readln(int &I){
    I=0;char C=getchar();bool f=0;
    while (!isdigit(C))f|=(C=='-'),C=getchar();
    while ( isdigit(C))(I*=10)+=(C-'0'),C=getchar();
    if(f)I=-I;
}
void assert(bool P){if(!P)puts("fkccf");}
int a[100005],n,m,p;
#define ull unsigned long long
#define cur (*cr)
struct C{
    ull v;
    C(){v=0;}C(ull V){v=V;}
};
C operator+ (C ca,C cb){return (ca.v+cb.v)%p;}
C operator+=(C&ca,C cb){return ca=ca+cb;}
C operator* (C ca,C cb){return (ca.v*cb.v)%p;}
C operator*=(C&ca,C cb){return ca=ca*cb;}
struct node{
    int l,r;
    C sum,t2,t1;
    node *ls=NULL,*rs=NULL;
    node(int _L,int _R,C _S,C _A,C _T,node*L,node*R){
        l=_L,r=_R,
        sum=_S,t2=_A,t1=_T,ls=L,rs=R;
    }
    node(int _L,int _R,C _S){
        *this=node(_L,_R,_S,0,1,NULL,NULL);
    }
    node(){ }
};
int len(node&cr){return cr.r-cr.l+1;}
node operator~(node&cr){
    cr.sum*=cr.t1,
    cr.sum+=len(cr)*cr.t2;
    if(cr.ls!=NULL)
        (*cr.ls).t2*=cr.t1,
        (*cr.ls).t1*=cr.t1,
        (*cr.ls).t2+=cr.t2;
    if(cr.rs!=NULL)
        (*cr.rs).t2*=cr.t1,
        (*cr.rs).t1*=cr.t1,
        (*cr.rs).t2+=cr.t2;
    cr.t1=1,cr.t2=0;
    return cr;
}
node operator+(node&na,node&nb){
    ~na,~nb;
    assert(na.r+1==nb.l);
    assert(na.t1.v==1 and nb.t1.v==1 and na.t2.v==0 and nb.t2.v==0);
    return 
        node(na.l,nb.r,na.sum+nb.sum,0,1,&na,&nb);
}
struct segt{
    node*rt;
    void init(int*a,int l,int r){
        rt=new node;build(a,rt,l,r);
    }
    void build(int*a,node*o,int l,int r){
        if(l==r)
            *o=node(l,r,a[l]);
        else {
            int mid=((l+r)>>1);
            node *lson=new node,*rson=new node;
            build(a,lson,l,mid),build(a,rson,mid+1,r),*o=*lson+*rson;
        }
    }
    void add(node*cr,int&l,int&r,int&val){
        if(cr==NULL or r<cur.l or l>cur.r)return;
        ~cur;
        if(l<=cur.l and cur.r<=r)
            cur.t2+=val;
        else 
            add(cur.ls,l,r,val),add(cur.rs,l,r,val),*cr=*cur.ls+*cur.rs;
    }   
    void add(int&l,int&r,int&val){return add(rt,l,r,val);}
    void tim(node*cr,int&l,int&r,int&val){
        if(cr==NULL or r<cur.l or l>cur.r)return;
        ~cur;
        if(l<=cur.l and cur.r<=r)
            cur.t1*=val,cur.t2*=val;
        else 
            tim(cur.ls,l,r,val),tim(cur.rs,l,r,val),*cr=*cur.ls+*cur.rs;
    }
    void tim(int&l,int&r,int&val){return tim(rt,l,r,val);}
    C que(node*cr,int&l,int&r){
        if(cr==NULL or r<cur.l or l>cur.r)return 0;
        ~cur;
        if(l<=cur.l and cur.r<=r)
            return cur.sum;
        else 
            return que(cur.ls,l,r)+que(cur.rs,l,r);
    }
}Tr;
int main(){
    #ifdef LOCAL
    freopen(".\\..\\..\\dt\\P3373_2.in","r",stdin);
    freopen("out.txt","w",stdout);
    std::chrono::milliseconds Clock1, Clock2;
    Clock1 = std::chrono::duration_cast< std::chrono::milliseconds >(
			std::chrono::system_clock::now().time_since_epoch()
			);
    #endif
    readln(n),readln(m),readln(p);
    for(int i=1;i<=n;i++)
        readln(a[i]);
    Tr.init(a,1,n);
    while(m--){
        int op,u,v,w;
        readln(op),readln(u),readln(v);
        switch (op){
        case 1:readln(w),Tr.tim(Tr.rt,u,v,w);break;
        case 2:readln(w),Tr.add(Tr.rt,u,v,w);break;
        case 3:printf("%llu\n",Tr.que(Tr.rt,u,v).v);break;
        }
    }
    #ifdef LOCAL
    Clock2 = std::chrono::duration_cast< std::chrono::milliseconds >(
                    std::chrono::system_clock::now().time_since_epoch()
                    );
    fclose(stdout);
    freopen("con","w",stdout);
    printf("%lld\n",(Clock2-Clock1).count());
    #endif
}