记录编号	577209	评测结果	AAAATTTTTT
题目名称	3738.逆元数列	最终得分	40
用户昵称	lihaoze	是否通过	未通过
代码语言	C++	运行时间	6.144 s
提交时间	2022-10-25 23:43:40	内存使用	19.97 MiB

#include "bits/stdc++.h"

using i64 = long long;

struct Seg {
    int l, r;
    i64 sum, ins, cnt, flag, same;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define sum(x) tree[x].sum
    #define ins(x) tree[x].ins
    #define cnt(x) tree[x].cnt
    #define flag(x) tree[x].flag
    #define len(x) (r(x) - l(x) + 1)
};

const int N = 1e5 + 10;
int n, m;
i64 a[N];
Seg tree[4 * N];

i64 P;

i64 power(i64 a, i64 b, i64 p) {
    i64 ret = 1;
    for (; b; b /= 2, a = a * a % p) 
        if (b % 2) ret = ret * a % p;
    return ret % p;
}

i64 inv(i64 a, i64 p) {
    return power(a, p - 2, p);
}

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if (l == r) 
        return sum(p) = a[l], ins(p) = inv(a[l], P), cnt(p) = 1, void();
    int mid = l + r >> 1;
    build(p * 2, l, mid),
    build(p * 2 + 1, mid + 1, r);
    sum(p) = sum(p * 2) + sum(p * 2 + 1); 
    ins(p) = ins(p * 2) + ins(p * 2 + 1);
    cnt(p) = cnt(p * 2) + cnt(p * 2 + 1);
}

void spread(int x) {
    if (flag(x)) {
        cnt(x * 2) = len(x * 2) - cnt(x * 2);
        cnt(x * 2 + 1) = len(x * 2 + 1) - cnt(x * 2 + 1);
        flag(x * 2) = flag(x * 2 + 1) = true;
        flag(x) = false;
    }
}

void change(int p, int l, int r) {
    if (l <= l(p) && r >= r(p)) {
        cnt(p) = len(p) - cnt(p), flag(p) = true;
        return;
    }
    if (r < l(p) || l > r(p)) return;
    spread(p);
    change(p * 2, l, r), change(p * 2 + 1, l, r);
    cnt(p) = cnt(p * 2) + cnt(p * 2 + 1);
}

i64 ask(int p, int l, int r) {
    if (l <= l(p) && r >= r(p) && (!cnt(p) || !(len(p) - cnt(p)))) 
        return cnt(p) ? sum(p) : ins(p);
    if (r < l(p) || l > r(p)) return 0;
    spread(p);
    i64 res = ask(p * 2, l, r) + ask(p * 2 + 1, l, r);
    return res;
}

void debug() {
    for (int i = 1; i <= n; ++ i) 
        ask(1, i, i);
    return;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    freopen("invarray.in", "r", stdin); 
    freopen("invarray.out", "w", stdout);
    std::cin >> n >> m >> P;
    for (int i = 1; i <= n; ++ i) 
        std::cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; ++ i) {
        int op, l, r;
        std::cin >> op >> l >> r;
        if (op == 1) {
            change(1, l, r), debug();
        } else {
            std::cout << ask(1, l, r) << '\n';
        }
    }
    return 0;
}