QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#844019#9774. Same SumarcaWA 574ms59348kbC++204.9kb2025-01-05 11:51:072025-01-05 11:51:07

Judging History

你现在查看的是最新测评结果

  • [2025-01-11 11:59:18]
  • hack成功,自动添加数据
  • (/hack/1443)
  • [2025-01-05 11:51:07]
  • 评测
  • 测评结果:WA
  • 用时:574ms
  • 内存:59348kb
  • [2025-01-05 11:51:07]
  • 提交

answer

#include <iostream>
#include <numeric>
#include <random>
#include <vector>

using i64 = long long;

bool isPrime(i64 n) {
    if (n == 1) return false;
    for (i64 i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int n, q;
i64 M, P, iP, P2, iP2;
std::uniform_int_distribution<i64> RNG(1e5, 1e6), RNG2(1e5, 1e6);
std::mt19937_64 mt(std::random_device{}());

i64 fpow(i64 a, i64 b, i64 p = M) {
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

struct Node {
    i64 Mp, Mm;
    i64 Mp2, Mm2;
    i64 sum, len;
    i64 tag;
    Node(i64 Mp = 0, i64 Mm = 0, i64 Mp2 = 0, i64 Mm2 = 0, i64 sum = 0,
         i64 len = 0, i64 tag = 0)
        : Mp(Mp),
          Mm(Mm),
          Mp2(Mp2),
          Mm2(Mm2),
          sum(sum),
          len(len),
          tag(tag) {}
    Node operator+(const Node &rhs) const {
        return Node((Mp + rhs.Mp) % M,
                    (Mm + rhs.Mm) % M,
                    (Mp2 + rhs.Mp2) % M,
                    (Mm2 + rhs.Mm2) % M,
                    sum + rhs.sum,
                    len + rhs.len,
                    tag + rhs.tag);
    }
};
std::vector<Node> T;
std::vector<i64> a;

void pullup(int p) {
    T[p].Mp  = (T[p << 1].Mp + T[p << 1 | 1].Mp) % M;
    T[p].Mm  = (T[p << 1].Mm + T[p << 1 | 1].Mm) % M;
    T[p].Mp2 = (T[p << 1].Mp2 + T[p << 1 | 1].Mp2) % M;
    T[p].Mm2 = (T[p << 1].Mm2 + T[p << 1 | 1].Mm2) % M;
    T[p].sum = T[p << 1].sum + T[p << 1 | 1].sum;
    T[p].len = T[p << 1].len + T[p << 1 | 1].len;
}
void maketag(int p, int l, int r, i64 v, i64 Pv, i64 iPv, i64 P2v,
             i64 iP2v) {
    T[p].sum += v * (r - l + 1);
    T[p].Mp  = T[p].Mp * Pv % M;
    T[p].Mm  = T[p].Mm * iPv % M;
    T[p].Mp2 = T[p].Mp2 * P2v % M;
    T[p].Mm2 = T[p].Mm2 * iP2v % M;
    T[p].tag += v;
}
void pushdown(int p, int l, int r, i64 v, i64 Pv, i64 iPv, i64 P2v,
              i64 iP2v) {
    if (!T[p].tag) return;
    int mid = std::midpoint(l, r);
    maketag(p << 1, l, mid, v, Pv, iPv, P2v, iP2v);
    maketag(p << 1 | 1, mid + 1, r, v, Pv, iPv, P2v, iP2v);
    T[p].tag = 0;
}
void Build(int p = 1, int l = 0, int r = n - 1) {
    if (l == r) {
        T[p] = Node(fpow(P, a[l]),
                    fpow(iP, a[l]),
                    fpow(P2, a[l]),
                    fpow(iP2, a[l]),
                    a[l],
                    1,
                    0);
        return;
    }
    int mid = std::midpoint(l, r);
    Build(p << 1, l, mid);
    Build(p << 1 | 1, mid + 1, r);
    pullup(p);
}
void Modify(int ql, int qr, i64 v, i64 Pv, i64 iPv, i64 P2v, i64 iP2v,
            int p = 1, int l = 0, int r = n - 1) {
    if (ql <= l && r <= qr) {
        maketag(p, l, r, v, Pv, iPv, P2v, iP2v);
        return;
    }
    int mid = std::midpoint(l, r);
    // pushdown(p,
    //          l,
    //          r,
    //          T[p].tag,
    //          fpow(P, T[p].tag),
    //          fpow(iP, T[p].tag),
    //          fpow(P2, T[p].tag),
    //          fpow(iP2, T[p].tag));
    if (ql <= mid) Modify(ql, qr, v, Pv, iPv, P2v, iP2v, p << 1, l, mid);
    if (qr > mid)
        Modify(ql, qr, v, Pv, iPv, P2v, iP2v, p << 1 | 1, mid + 1, r);
    pullup(p);
}
Node query(int ql, int qr, int p = 1, int l = 0, int r = n - 1) {
    if (ql <= l && r <= qr) return T[p];
    int mid = std::midpoint(l, r);
    pushdown(p,
             l,
             r,
             T[p].tag,
             fpow(P, T[p].tag),
             fpow(iP, T[p].tag),
             fpow(P2, T[p].tag),
             fpow(iP2, T[p].tag));
    if (qr <= mid) return query(ql, qr, p << 1, l, mid);
    else if (ql > mid) return query(ql, qr, p * 2 + 1, mid + 1, r);
    else
        return query(ql, qr, p << 1, l, mid) +
               query(ql, qr, p * 2 + 1, mid + 1, r);
}

int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
    P = RNG(mt), M = RNG2(mt), P2 = RNG(mt);
    while (!isPrime(P)) P++;
    while (!isPrime(M)) M++;
    while (!isPrime(P2)) P2++;
    iP  = fpow(P, M - 2, M);
    iP2 = fpow(P2, M - 2, M);

    std::cin >> n >> q;
    T.resize(n * 5);
    a.resize(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];

    Build();

    while (q--) {
        int op, l, r;
        std::cin >> op >> l >> r;
        if (op == 1) {
            i64 x;
            std::cin >> x;
            Modify(l - 1,
                   r - 1,
                   x,
                   fpow(P, x),
                   fpow(iP, x),
                   fpow(P2, x),
                   fpow(iP2, x));
        } else {
            auto res = query(l - 1, r - 1);
            auto fp  = fpow(P, res.sum / (res.len / 2));
            if (res.Mp % M == res.Mm * fp % M) std::cout << "YES\n";
            else std::cout << "NO\n";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8

output:

YES
NO
YES

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: -100
Wrong Answer
time: 574ms
memory: 59348kb

input:

200000 200000
0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected YES, found NO [464th token]