样例过的好好的，交上去全 TLE 了，明天 NOIP 害怕也遇到这种情况/lyj

哪位大佬帮忙看看

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

#define $int long long

/***** Fast_IO *****/

using std::cin;
using std::cout;
using vii = std::vector<int> ;
using pii = std::pair<int,int> ;

namespace IO{
	char buf[(1<<21)],*p1=buf,*p2=buf,buf1[(1<<21)]; int _=0;

	inline char gc (){
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<21),stdin),p1==p2)?EOF:*p1++;
	}

	#define gc getchar
	#define pc putchar
	#define ONLINE_JUDGE OJ

	template<class I>
	inline I read(I &x){
		x=0; I f=1; char c=gc(); if(c==EOF){ return -1; }
		while(c<'0'||c>'9'){ if(c=='-'){ f=f*(-1); } c=gc(); }
		while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=gc(); }
		return x=x*f;
	}

	template<typename I,typename ...Args>
	inline void read(I &a, Args &...args){
		read(a),read(args...);
	}

	template<class I>
	inline void write(I x){
		if(x==0){ pc('0'); return; }
		int tmp=x>0?x:(-x),cnt=0;
		if(x<0){ pc('-'); }
		while(tmp){ buf[cnt++]=(tmp%10)+'0'; tmp/=10; }
		while(cnt){ pc(buf[--cnt]); }
		return;
	}

	void _FILE(){
		#ifndef ONLINE_JUDGE
			freopen("text.in","r",stdin);
			freopen("text.out","w",stdout);
		#endif
	}
	
	template<class I>
	inline void chmax(I &x,I y){ return x=max(x,y),void(); }
	
	template<class I>
	inline void chmin(I &x,I y){ return x=min(x,y),void(); }

	#define out(x) write(x),pc(' ')
	#define outn(x) write(x),pc('\n')
	#define assi() pc('\t')
	#define FOR(i,a,b) for(int i(a);i<=(b);++i)
	#define ROF(i,a,b) for(int i(a);i>=(b);--i)
	#define FORs(i,a,b,s) for(int i(a);i<=(b);i+=(s))
	#define ROFs(i,a,b,s) for(int i(a);i>=(b);i-=(s))
	#define next(i,now) for(int i(link[now]);i;i=edge[i].nexty)
	#define each(i,v) for(auto &i:v)
	#define all(v) v.begin(),v.end()
	#define sqr(k) ((k)*(k))
	#define inf 0x3f3f3f3f
	#define pb push_back
	#define mp make_pair
	#define fir first
	#define sec second
}using namespace IO;

/***** Fast_IO *****/

#define maxn 1000010
#define SIZE 5010

int mod;

int arr[maxn];

class Splay_Fold{
	private:
		struct SP_tree{ int son[2],fa,cnt,size,val,add_lazy,pro_lazy,sum; }tree[maxn];
		
		int tree_cnt,root;
		
	public:
		void pushup(int ID){
			tree[ID].size=tree[tree[ID].son[0]].size+tree[tree[ID].son[1]].size;
			tree[ID].sum=tree[tree[ID].son[0]].sum+tree[tree[ID].son[1]].sum+arr[ID-1];
		}
		
		int Son(int ID){ return tree[tree[ID].fa].son[1]==ID; }
		
		void connect(int x,int y,int k){
			if(x){ tree[x].son[k]=y; }
			tree[y].fa=x;
		}
		
		void rotate(int ID){
			int fa(tree[ID].fa),gra_fa(tree[fa].fa);
			int ty_son(Son(ID)),ty_fa(Son(fa));
			connect(fa,tree[ID].son[ty_son^1],ty_son);
			connect(ID,fa,ty_son^1);
			connect(gra_fa,ID,ty_fa);
			pushup(fa);
			pushup(ID);
		}
		
		void Splay(int ID,int goal=0){
			for(int index;(index=tree[ID].fa)!=goal;rotate(ID)){
				if(tree[index].fa!=goal){
					if(Son(index)==Son(ID)){
						rotate(index);
					} else{ rotate(ID); }
				}
			} if(goal==0){ root=ID; }
			return;
		}
		
		int NewNode(int val){
			tree[++tree_cnt]=(SP_tree){ {0,0},0,1,1,val,0,1,arr[val-1] };
			return tree_cnt;
		}
		
		void insert(int val){
			if(!root){ root=NewNode(val); return; }
			int index=root;
			while(tree[index].val!=val&&tree[index].son[tree[index].val<val]){
				index=tree[index].son[tree[index].val<val];
			} if(tree[index].val==val){ ++tree[index].cnt; Splay(index); return; }
			connect(index,NewNode(val),tree[index].val<val);
			Splay(tree[index].son[tree[index].val<val]);
			return;
		}
		
		void find(int val){
			int index=root;
			while(tree[index].val!=val&&tree[index].son[tree[index].val<val]){
				index=tree[index].son[tree[index].val<val];
			} return Splay(index);
		}
		
		void pushdown(int ID){
			(tree[tree[ID].son[0]].add_lazy=(tree[tree[ID].son[0]].add_lazy*tree[ID].pro_lazy+tree[ID].add_lazy))%=mod;
			(tree[tree[ID].son[1]].add_lazy=(tree[tree[ID].son[1]].add_lazy*tree[ID].pro_lazy+tree[ID].add_lazy))%=mod;
			(tree[tree[ID].son[0]].pro_lazy=(tree[tree[ID].son[0]].pro_lazy*tree[ID].pro_lazy))%=mod;
			(tree[tree[ID].son[1]].pro_lazy=(tree[tree[ID].son[1]].pro_lazy*tree[ID].pro_lazy))%=mod;
			(tree[tree[ID].son[0]].sum=(tree[tree[ID].son[0]].sum*tree[ID].pro_lazy+tree[tree[ID].son[0]].size*tree[ID].add_lazy))%=mod;
			(tree[tree[ID].son[1]].sum=(tree[tree[ID].son[1]].sum*tree[ID].pro_lazy+tree[tree[ID].son[1]].size*tree[ID].add_lazy))%=mod;
			(arr[tree[ID].son[0]-1]=(arr[tree[ID].son[0]-1]*tree[ID].pro_lazy+tree[ID].add_lazy))%=mod;
			(arr[tree[ID].son[1]-1]=(arr[tree[ID].son[1]-1]*tree[ID].pro_lazy+tree[ID].add_lazy))%=mod;
			tree[ID].add_lazy=0,tree[ID].pro_lazy=1;
		}
		
		int get_num(int rk){
			int index=root;
			while(19260817){
				pushdown(index);
				if(tree[tree[index].son[0]].size>=rk){
					index=tree[index].son[0];
				} else if(tree[tree[index].son[0]].size+tree[index].cnt<rk){
					rk-=(tree[tree[index].son[0]].size+tree[index].cnt);
					index=tree[index].son[1];
				} else{ break; }
			} return index;
		}
		
		void add_update(int l,int r,int val){
			l=get_num(l),r=get_num(r+2);
			Splay(l,0),Splay(r,l);
			int rt=tree[tree[root].son[1]].son[0];
			(tree[rt].add_lazy+=val)%=mod;
			(tree[rt].sum+=tree[rt].size*val)%=mod;
			(arr[rt-1]+=val)%=mod;
			pushup(tree[root].son[1]);
			pushup(root);
			return;
		}
		
		void pro_update(int l,int r,int val){
			l=get_num(l),r=get_num(r+2);
			Splay(l,0),Splay(r,l);
			int rt=tree[tree[root].son[1]].son[0];
			(tree[rt].add_lazy*=val)%=mod;
			(tree[rt].pro_lazy*=val)%=mod;
			(tree[rt].sum*=val)%=mod; 
			(arr[rt-1]*=val)%=mod;
			pushup(tree[root].son[1]);
			pushup(root);
			return;
		}
		
		int query(int l,int r){
			l=get_num(l),r=get_num(r+2);
			Splay(l,0),Splay(r,l);
			int rt=tree[tree[root].son[1]].son[0];
			return tree[rt].sum;
		}
}sp;

int n,m;

int main(){
	read(n,m,mod);
	FOR(i,1,n){ read(arr[i]); }
	FOR(i,1,n+2){ sp.insert(i); }
	while(m--){
		int opt=read(_);
		switch(opt){
			case 1:{
				int x,y,k;
				read(x,y,k);
				sp.add_update(x,y,k);
				break;
			} case 2:{
				int x,y,k;
				read(x,y,k);
				sp.pro_update(x,y,k);
				break;
			} case 3:{
				int x,y;
				read(x,y);
				outn( sp.query(x,y) );
				break;
			}
		}
	}
	return 0;
}