记录编号	326939	评测结果	AWAWTTTTEE
题目名称	学姐的巧克力盒	最终得分	20
用户昵称	ciyou	是否通过	未通过
代码语言	C++	运行时间	9.095 s
提交时间	2016-10-21 17:43:18	内存使用	27.75 MiB

    #include<iostream>
    #include<cstdio>
    #define ll long long
    using namespace std;
    ll sigtree[4000006];
    int N,M,K,P1,P2;
    ll ask(int,int,int,int,int);
    ll ask_again(int,int,int,int,int);
    ll PowerMod(int a, int b, int c){
    	int ans = 1;
    	a = a % c;
    	while(b>0){
    		if(b%2==1)
    			ans=(ans*a)%c;
    		b=b/2;
    		a=(a*a)%c;
    	}
    	return ans;
    }
    int main(){
    	freopen("chocolatebox.in","r",stdin);
    	freopen("chocolatebox.out","w",stdout);
    	cin>>N>>M>>K>>P1>>P2;
    	int k=1;
    	while((1<<k)<N) k++;
    	int MAXN=1<<k;
    	for(int i=1;i<=N;i++){
    		int t;
    		cin>>t;
    		sigtree[MAXN+i-1]=t%P1;
    	}
    	if(N<MAXN) for(int i=MAXN+N;i<=MAXN*2-1;i++) sigtree[i]=1;
    	k=(MAXN/2);
    	while(k>0){
    		for(int i=k;i<(k*2);i++){
    			ll temp;
    			temp=(sigtree[i<<1]*sigtree[(i<<1)|1])%P1;
    			sigtree[i]=temp;
    		}
    		k=(k/2);
    	}
    	for(int i=1;i<=M;i++){
    		int ty,l,r;
    		cin>>ty>>l>>r;
    		if(ty==1) cout<<ask(l,r,1,MAXN,1)<<endl;
    		if(ty==2) cout<<PowerMod(K,ask_again(l,r,1,MAXN,1),P2);
    	}
    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    }
    ll ask(int l,int r,int a,int b,int k){
    	int m=(a+b)/2;
    	if(l==a&&r==b) {
    		return sigtree[k];
    	}
    	if(m>=r) return ask(l,r,a,m,k<<1);
    	if(m+1<=l) return ask(l,r,m+1,b,k<<1|1);
    	
    	ll temp=(ask(l,m,a,m,k<<1)*ask(m+1,r,m+1,b,k<<1|1))%P1;
    	int ans=temp;
    	return ans;
    }
    ll ask_again(int l,int r,int a,int b,int k){
    	int m=(a+b)/2;
    	if(l==a&&r==b) {
    		return sigtree[k];
    	}
    	if(m>=r) return ask(l,r,a,m,k<<1);
    	if(m+1<=l) return ask(l,r,m+1,b,k<<1|1);
    	
    	ll temp=(ask(l,m,a,m,k<<1)*ask(m+1,r,m+1,b,k<<1|1))%P2;
    	int ans=temp;
    	return ans;
    }