求条教伸展树70ptsTLE

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,mod;
struct ww{
    int son[2]={0,0};
    int fa=0,y1=0,y2=1,size=1,name=0,sum=0,I;
}rt[200005];
int in[200005];
int tot=0;
void updata(int x){
    if(!x)return;
    rt[x].size=1;
    rt[x].sum=rt[x].I;
	if(rt[x].son[0])rt[x].size+=rt[rt[x].son[0]].size;
	if(rt[x].son[1])rt[x].size+=rt[rt[x].son[1]].size;
	if(rt[x].son[0])(rt[x].sum+=rt[rt[x].son[0]].sum)%=mod;
	if(rt[x].son[1])(rt[x].sum+=rt[rt[x].son[1]].sum)%=mod;
    return;
}
void maketag1(int x,int d){
    if(!x)return;
    (rt[x].sum+=d*rt[x].size%mod)%=mod;
    (rt[x].I+=d)%=mod;
	(rt[x].y1+=d)%=mod;
	return;
}
void maketag2(int x,int d){
    if(!x)return;
    (rt[x].sum*=d)%=mod;
    (rt[x].I*=d)%=mod;
	(rt[x].y1*=d)%=mod;
	(rt[x].y2*=d)%=mod;
	return;
}
void pushdown(int x){
    if(rt[x].son[0])maketag2(rt[x].son[0],rt[x].y2),maketag1(rt[x].son[0],rt[x].y1);
    if(rt[x].son[1])maketag2(rt[x].son[1],rt[x].y2),maketag1(rt[x].son[1],rt[x].y1);
    rt[x].y1=0,rt[x].y2=1;
    return;
}
void print(int x){
    // if(rt[x].son[0])cout<<rt[x].name<<' '<<rt[rt[x].son[0]].name<<' '<<0<<endl;
    // if(rt[x].son[1])cout<<rt[x].name<<' '<<rt[rt[x].son[1]].name<<' '<<1<<endl;
    if(rt[x].son[0])print(rt[x].son[0]);
    cout<<rt[x].name<<' '<<rt[x].I<<' '<<rt[x].y1<<' '<<rt[x].y2<<endl;
    if(rt[x].son[1])print(rt[x].son[1]);
    return;
}
int Rotate(int x){
	// cout<<"ROTATE::"<<rt[x].name<<rt[rt[x].fa].name<<endl;
    if(rt[x].fa==0)return x;
    int y=rt[x].fa,z=rt[y].fa;
    pushdown(z);pushdown(y),pushdown(x);
    int op=(rt[y].son[1]==x);
    rt[y].son[op]=rt[x].son[!op];
    rt[rt[x].son[!op]].fa=y;
    rt[x].son[!op]=y;
    rt[y].fa=x;
    rt[x].fa=z;
    rt[z].son[rt[z].son[1]==y]=x;
    updata(y),updata(x);if(z)updata(z);
    return x;
}
int Splay(int x,int Up){
	//cout<<"SPLAy::"<<rt[x].name<<' '<<rt[Up].name<<endl;
    
		// print(0);cout<<endl<<endl;
    while(rt[rt[x].fa].fa!=Up&&rt[x].fa!=Up&&rt[rt[x].fa].fa&&rt[x].fa){
        int y=rt[x].fa,z=rt[y].fa;
        if(!((rt[y].son[0]==x)^(rt[z].son[0]==y)))Rotate(y);else Rotate(x);
		// print(0);cout<<"=="<<endl<<endl;
        
        Rotate(x);
		// print(0);cout<<"=="<<endl<<endl;
    }
    if(rt[x].fa!=Up){
        Rotate(x);
        // print(0);cout<<endl<<endl;
    }
    return x;
}
int Find(int Fa,int rank){
	// cout<<"FIND::"<<Fa<<' '<<rank<<endl;
		// print(0);cout<<endl<<endl;
    int x=rt[0].son[0];
    while(rank){
        pushdown(x);
    	int wei=rt[rt[x].son[0]].size+1;
    // cout<<Fa<<' '<<rank<<' '<<rt[x].name<<endl;
	    if(rank==wei){
	        Splay(x,Fa);
            // cout<<"RETURN::"<<rt[x].name<<endl;
	        return x;
	    }else if(rank<wei){
	    	x=rt[x].son[0];
	    }else{
	        rank-=wei;
	        x=rt[x].son[1];
	    }
	}
    return 0;
}
int build(int l,int r,int fa){
    if(r<l){
        return 0;
    }
    int mid=(l+r)>>1;
    int my=++tot;
    rt[my].son[0]=build(l,mid-1,my);
    rt[my].son[1]=build(mid+1,r,my);
    rt[my].name=mid;
    rt[my].fa=fa;
    rt[my].I=in[rt[my].name];
    updata(my);
//     cout<<rt[my].name<<' '<<rt[rt[my].son[0]].name<<' '<<rt[rt[my].son[1]].name<<endl;
    return rt[0].son[0]=my;
}
void qujian1(int l,int r,int k){
	Find(0,l-1);
	Find(rt[0].son[0],r+1);
	maketag1(rt[rt[rt[0].son[0]].son[1]].son[0],k);
	return;
}
void qujian3(int l,int r,int k){
	Find(0,l-1);
	Find(rt[0].son[0],r+1);
	maketag2(rt[rt[rt[0].son[0]].son[1]].son[0],k);
	return;
}
int qujian2(int l,int r){
	Find(0,l-1);
	Find(rt[0].son[0],r+1);
	return rt[rt[rt[rt[0].son[0]].son[1]].son[0]].sum;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    rt[0].size=0;
    rt[0].name=-1;
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++){
        cin>>in[i];
    }
    build(0,n+1,0);
    for(int i=1;i<=m;i++){
        // print(0);
    	int l,r,op,k;
    	cin>>op>>l>>r;
        if(op==2){
            cin>>k;
            qujian1(l+1,r+1,k);
        }else if(op==1){
            cin>>k;
            qujian3(l+1,r+1,k);
        }else cout<<qujian2(l+1,r+1)<<endl;
	}
    return 0;
}