比赛 2024暑假C班集训E 评测结果 TTTTTTTTTTTTWWWWTTTT
题目名称 相逢是问候 最终得分 0
用户昵称 darkMoon 运行时间 48.093 s
代码语言 C++ 内存使用 3.68 MiB
提交时间 2024-07-14 11:45:56
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
// #define fin cin
// #define fout cout
ifstream fin("verbinden.in");
ofstream fout("verbinden.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 5e4 + 5, Q = 255;
int n = mread(), m = mread();
const int MOD = mread();
int c = mread(), a[N], q, belong[N], pw[35];
int ksm(int x, int k){
    int ans = 1, now = x;
    while(k){
        if(k & 1){
            ans = ans * now % MOD;
        }
        now = now * now % MOD;
        k >>= 1;
    }
    return ans;
}
struct node{
    int sum[35] = {0}, tmp = 0, l = 0, r = 0;
    void make(){
        for(int i = l; i <= r; i ++){
            (sum[0] += a[i]) %= MOD;
        }
        int now = 1;
        for(int i = 1; i <= 30; i ++){
            for(int j = l; j <= r; j ++){
                (sum[i] += ksm(pw[i], a[j])) %= MOD;
            }
        }
        return;
    }
    void ch(int nl, int nr){
        for(int i = l; i <= r; i ++){
            if(i >= nl && i <= nr){
                if(tmp >= 29){
                    a[i] = pw[30];
                }
                else{
                    a[i] = ksm(pw[tmp + 1], a[i]);
                }
            }
            else{
                if(tmp >= 30){
                    a[i] = pw[30];
                }
                else{
                    if(tmp == 0);
                    else{
                        a[i] = ksm(pw[tmp], a[i]);
                    }
                }
            }
        }
        tmp = 0;
        make();
    }
}s[Q];
void ch(int l, int r){
    int x = belong[l], y = belong[r];
    if(x == y){
        s[x].ch(l, r);
        return;
    }
    for(int i = x + 1; i < y; i ++){
        s[i].tmp ++;
    }
    s[x].ch(l, s[x].r);
    s[y].ch(s[y].l, r);
    return;
}
int query(int l, int r){
    int x = belong[l], y = belong[r], ans = 0;
    if(x == y){
        s[x].ch(0, 0);
        for(int i = l; i <= r; i ++){
            (ans += a[i]) %= MOD;
        }
        return ans;
    }
    for(int i = x + 1; i < y; i ++){
        (ans += s[i].sum[min(30ll, s[i].tmp)]) %= MOD;
    }
    s[x].ch(0, 0);
    for(int i = l; i <= s[x].r; i ++){
        (ans += a[i]) %= MOD;
    }
    s[y].ch(0, 0);
    for(int i = s[y].l; i <= r; i ++){
        (ans += a[i]) %= MOD;
    }
    return ans;
}
signed main(){
    pw[0] = 1;
    for(int i = 1; i <= 30; i ++){
        pw[i] = ksm(c, pw[i - 1]);
    }
    for(int i = 1; i <= n; i ++){
        a[i] = mread();
    }
    q = sqrt(n);
    for(int i = 1; i <= q; i ++){
        s[i].l = s[i - 1].r + 1;
        s[i].r = s[i].l + q - 1;
    }
    s[q].r = n;
    for(int i = 1; i <= q; i ++){
        for(int j = s[i].l; j <= s[i].r; j ++){
            belong[j] = i;
        }
        s[i].make();
    }
    // for(int i = 1; i <= q; i ++){
    //     for(int j = 0; j <= 3; j ++){
    //         printf("%lld ", s[i].sum[j]);
    //     }
    //     printf("\n");
    // }
    while(m --){
        int op = mread(), l = mread(), r = mread();
        if(op == 0){
            ch(l, r);
        }
        else{
            fout << query(l, r) << "\n";
        }
        // printf("***\n");
        // for(int i = 1; i <= n; i ++){
        //     printf("%lld ", a[i]);
        // }
        // printf("\n");
    }
    return 0;
}