如题，时间复杂度两个 $\log$ 且已在 LOJ 上通过。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e4+114;
const int maxp = 2e4+114;
const int maxlg = 120;
int n,m,p,c;
int maxLG;
int phi(int n){
  	int m=(int)(sqrt(n+0.5));
 	int ans=n;
    for(int i=2;i<=m;i++){
    	if(n%i==0){
      		ans=ans/i*(i-1);
      		while (n%i==0) n/=i;
    	}
    }
  	if(n>1) ans=ans/n*(n-1);
  	return ans;
}
int PHI[maxlg],NOW[maxlg];
int _pow[maxlg][maxp];
int Bigpow[maxlg][maxp];//10^4 为基础开始处理
int b[maxn][10],mx[maxn];
struct Node{
	int cnt,sum;
}tr[maxn<<2];
void pushup(int cur){
	tr[cur].cnt=min(tr[cur<<1].cnt,tr[cur<<1|1].cnt);
	tr[cur].sum=tr[cur<<1].sum+tr[cur<<1|1].sum;
}
int a[maxn];
void build(int cur,int lt,int rt){
	if(lt==rt){
		tr[cur].sum=a[lt];
		tr[cur].cnt=0;
		return ;
	}
	int mid=(lt+rt)>>1;
	build(cur<<1,lt,mid);
	build(cur<<1|1,mid+1,rt);
	pushup(cur);
	return ;
}
inline int ChiFAN(int s,int val){
    if(val==0) return 1;
    int res=val/10000;
    val%=10000;
    int ans=Bigpow[s][res];
    ans=(ans*_pow[s][val])%NOW[s];
    return ans;
}
inline int solve(int pos,int cnt,int s){//位置是 pos c 的1数量是 cnt
	if(s>cnt) return a[pos];
	if(NOW[s]==1) return 0;
	int y=solve(pos,cnt,s+1);
	//cout<<"R:"<<c<<' '<<a[pos]<<' '<<s<<' '<<NOW[s]<<' '<<y<<'\n';
	if(cnt-s>=mx[pos]) return ChiFAN(s,y%PHI[s]+PHI[s]);
	else if(b[pos][cnt-s]>PHI[s]) return ChiFAN(s,y%PHI[s]+PHI[s]);
	else return ChiFAN(s,b[pos][cnt-s]);
}
inline void init(){
	int now=p;
	for(int i=1;i<maxlg;i++){
		PHI[i]=phi(now);
		NOW[i]=now;
		_pow[i][0]=1;
		for(int j=1;j<maxp;j++) _pow[i][j]=(_pow[i][j-1]*c)%now;
		Bigpow[i][0]=1;
		for(int j=1;j<maxp;j++) Bigpow[i][j]=(Bigpow[i][j-1]*_pow[i][10000])%now;
		now=PHI[i];
	}
}
inline void change(int cur,int lt,int rt,int ql,int qr){
	if(rt<ql||lt>qr) return;
	if(tr[cur].cnt>=maxlg-1) return ;
	if(lt==rt){
		tr[cur].cnt++;
		tr[cur].sum=solve(lt,tr[cur].cnt,1);
		//cout<<"R:"<<tr[cur].cnt<<' '<<tr[cur].sum<<'\n';
		return ;
	}
	int mid=(lt+rt)>>1;
	change(cur<<1,lt,mid,ql,qr);
	change(cur<<1|1,mid+1,rt,ql,qr);
	pushup(cur);
}
inline int ask(int cur,int lt,int rt,int ql,int qr){
	if(rt<ql||lt>qr) return 0;
	if(lt>=ql&&rt<=qr) return tr[cur].sum;
	int mid=(lt+rt)>>1;
	return (ask(cur<<1,lt,mid,ql,qr)+ask(cur<<1|1,mid+1,rt,ql,qr))%p;
}
inline int Pow(int a,int b){
	if(b==0) return 1;
	if(b==1) return a;
	int res=Pow(a,b/2);
	res=(res*res);
	if(b%2==1) res=(res*a);
	return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m>>p>>c;
	int x=1;
	for(int i=1;i<=60;i++){
        x*=c;
        if(x>100000000){
            maxLG=i;
            break;
        }
	}
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
        b[i][0]=a[i];
        for(int j=1;j<=9;j++){
            if(b[i][j-1]>=maxLG){
                mx[i]=j;
                break;
            }
            else b[i][j]=Pow(c,b[i][j-1]);
        }
	}
	build(1,1,n);
	init();
	//cout<<mx[1]<<'\n';
	while(m--){
		int op,l,r;
		cin>>op>>l>>r;
		if(op==0) change(1,1,n,l,r);
		else cout<<ask(1,1,n,l,r)<<'\n';
	}
	return 0;
}
/*
1 40 19910626 2
0
*/