比赛 2024暑假C班集训E 评测结果 TTTTTTTTTTTTWWWWTTTT
题目名称 相逢是问候 最终得分 0
用户昵称 djyqjy 运行时间 48.005 s
代码语言 C++ 内存使用 3.98 MiB
提交时间 2024-07-14 11:53:59
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n,m;
long long p,c;
long long a[N];
bool flag=1;
long long sum[N];
long long qpow(long long a,long long b)
{
    long long ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%p;
        b>>=1;
        a=(a*a)%p;
    }
    return ans;
}
long long cc[N];
void add(int w,long long x)
{
    while(w<=N)
    {
        cc[w]+=x;
        w+=w&-w;
    }
    return;
}
long long q(int w)
{
    long long ans=0;
    while(w)
    {
        ans+=cc[w];
        w-=w&-w;
    }
    return ans;
}
int main()
{
    freopen("verbinden.in","r",stdin);
    freopen("verbinden.out","w",stdout);
    scanf("%d%d%lld%lld",&n,&m,&p,&c);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
        add(i,a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==0)
        {
            flag=0;
            if(n<=100&&m<=100)
            {
                for(int j=l;j<=r;j++)
                    a[j]=qpow(c,a[j]);
            }
            else
            {
                for(int j=1;j<=r;j++)
                    add(j,qpow(c,a[j])-a[j]);
            }
        }
        else
        {
            if(flag) printf("%lld\n",((sum[r]-sum[l-1])%p+p)%p);
            else if(n<=100&&m<=100)
            {
                long long ans=0;
                for(int j=l;j<=r;j++)
                    ans=(ans+a[j])%p;
                printf("%lld\n",ans);
            }
            else printf("%lld\n",((q(r)-(l-1==0?0:q(l-1)))%p+p)%p);
        }
        for(int j=1;j<=n;j++)
            printf("%lld ",a[j]);
            printf("\n");
    }
    return 0;
}