比赛 2024暑假C班集训E 评测结果 WWTTTTTTTTTTTWTTTTTT
题目名称 相逢是问候 最终得分 0
用户昵称 Untitled 运行时间 52.433 s
代码语言 C++ 内存使用 3.74 MiB
提交时间 2024-07-14 11:02:53
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m;
ll p,c,res;
ll a[50010],t[50010];

ll Pow(ll x,ll a){
    if (!a) return 1;
    if (a==1) return x;
    if (a%2) return Pow(x,a/2)*Pow(x,a/2)*x;
    return Pow(x,a/2)*Pow(x,a/2);
}

int lowbit(int x){
    return x&-x;
}

void add(int x,ll a){
    while (x<=n){
        t[x]+=a,t[x]%=p,x+=lowbit(x);
    }
    return;
}

ll query(int x){
    ll cnt=0;
    while (x){
        cnt+=t[x],cnt%=p,x-=lowbit(x);
    }
    return cnt;
}

int main(){
    freopen("verbinden.in","r",stdin);
    freopen("verbinden.out","w",stdout);
    
    int k,l,r;
    scanf("%d %d %lld %lld",&n,&m,&p,&c);
    for (int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        add(i,a[i]);
    }
    if (n<=100 && m<=100){
        for (int x=1;x<=m;x++){
            scanf("%d %d %d",&k,&l,&r);
            if (!k){
                for (int i=l;i<=r;i++) a[i]=Pow(c,a[i]);
            }
            else{
                res=0;
                for (int i=l;i<=r;i++) res+=a[i],res%=p;
                printf("%lld\n",res);
            }
        }
    }
    else{
        for (int x=1;x<=m;x++){
            scanf("%d %d %d",&k,&l,&r);
            if (!k){
                ll w;
                for (int i=l;i<=r;i++){
                    w=Pow(c,a[i])-a[i];
                    add(i,w);
                }
            }
            else{
                res=query(r)-query(l-1);
                printf("%lld\n",res);
            }
        }
    }
    
    return 0;
}