QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#930635	#9774. Same Sum	Lyc-123	TL	355ms	30708kb	C++20	5.4kb	2025-03-10 01:47:56	2025-03-10 01:47:56

Judging History

This is the latest submission verdict.

[2025-03-10 01:47:56]
Judged

Verdict: TL
Time: 355ms
Memory: 30708kb

Show

[2025-03-10 01:47:56]
Submitted

answer

#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
#define endl '\n'
// #define uint64_t __int128_t
const int MAXN = 2e5 + 10;
const int SEED = 1e9 + 7;
const uint64_t MOD = 100000041894234263;
uint64_t pw[MAXN], rpw[MAXN];
uint64_t rseed;
uint64_t mpow(uint64_t a, uint64_t b) {
    // if (a == SEED && b < MAXN && pw[b]) return pw[b];
    uint64_t md = MOD;
    uint64_t ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = (__int128_t)ret * a % md;
        a = (__int128_t)a * a % md;
    }
    // if (a == SEED && b < MAXN) pw[b] = ret;
    return ret;
}

class SegmentTree {
    struct TreeNode {
        int l, r;
        uint64_t expr;
        uint64_t tag;
        uint64_t rev;
        uint64_t sum;
    } a[4 * MAXN];
    int val[MAXN];
    uint64_t seed;
public:
    SegmentTree() {
        seed = SEED;
    }
    void cat_val(int i, int x) { val[i] = x; }
    void build(int u, int l, int r) {
        a[u].l = l, a[u].r = r;
        if (l == r) {
            a[u].expr = pw[val[l]];
            a[u].rev = rpw[val[l]];
            a[u].sum = val[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        a[u].expr = (a[u << 1].expr + a[u << 1 | 1].expr) % MOD;
        a[u].rev = (a[u << 1].rev + a[u << 1 | 1].rev) % MOD;
        a[u].sum = (a[u << 1].sum + a[u << 1 | 1].sum);
    }
    void update(int u) {
        if (a[u].tag == 0) return;
        if (a[u].l == a[u].r) return;
        a[u << 1].tag += a[u].tag;
        a[u << 1 | 1].tag += a[u].tag;
        uint64_t pww, rpww;
        if (a[u].tag < MAXN) pww = pw[a[u].tag];
        else pww = mpow(SEED, a[u].tag);
        if (a[u].tag < MAXN) rpww = rpw[a[u].tag];
        else rpww = mpow(rseed, a[u].tag);
        a[u << 1].expr = (__int128_t)a[u << 1].expr * pww % MOD;
        a[u << 1 | 1].expr = (__int128_t)a[u << 1 | 1].expr * pww % MOD;
        a[u << 1].rev = (__int128_t)a[u << 1].rev * rpww % MOD;
        a[u << 1 | 1].rev = (__int128_t)a[u << 1 | 1].rev * rpww % MOD;
        a[u << 1].sum = a[u << 1].sum + (__int128_t)a[u].tag * (a[u << 1].r - a[u << 1].l + 1);
        a[u << 1 | 1].sum = a[u << 1 | 1].sum + (__int128_t)a[u].tag * (a[u << 1 | 1].r - a[u << 1 | 1].l + 1);
        a[u].tag = 0;
    }
    void add(int u, int l, int r, uint64_t w) {
        if (l <= a[u].l && r >= a[u].r) {
            a[u].expr = (__int128_t)a[u].expr * pw[w] % MOD;
            a[u].rev = (__int128_t)a[u].rev * rpw[w] % MOD;
            a[u].sum = a[u].sum + (__int128_t)w * (a[u].r - a[u].l + 1);
            a[u].tag += w;
            return;
        }
        update(u);
        int mid = (a[u].l + a[u].r) >> 1;
        if (l <= mid) add(u << 1, l, r, w);
        if (r > mid) add(u << 1 | 1, l, r, w);
        a[u].expr = (a[u << 1].expr + a[u << 1 | 1].expr) % MOD;
        a[u].rev = (a[u << 1].rev + a[u << 1 | 1].rev) % MOD;
        a[u].sum = (a[u << 1].sum + a[u << 1 | 1].sum);


    }
    uint64_t query_expr(int u, int l, int r) {
        if (l <= a[u].l && r >= a[u].r) return a[u].expr;
        update(u);
        int mid = (a[u].l + a[u].r) >> 1;
        uint64_t ret = 0;
        if (l <= mid) ret += query_expr(u << 1, l, r);
        if (r > mid) ret += query_expr(u << 1 | 1, l, r);
        return ret % MOD;
    }
    uint64_t query_rev(int u, int l, int r) {
        if (l <= a[u].l && r >= a[u].r) return a[u].rev;
        update(u);
        int mid = (a[u].l + a[u].r) >> 1;
        uint64_t ret = 0;
        if (l <= mid) ret += query_rev(u << 1, l, r);
        if (r > mid) ret += query_rev(u << 1 | 1, l, r);
        return ret % MOD;
    }
    uint64_t query_sum(int u, int l, int r) {
        if (l <= a[u].l && r >= a[u].r) return a[u].sum;
        update(u);
        int mid = (a[u].l + a[u].r) >> 1;
        uint64_t ret = 0;
        if (l <= mid) ret += query_sum(u << 1, l, r);
        if (r > mid) ret += query_sum(u << 1 | 1, l, r);
        return ret;
    }
} SegTree1;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        SegTree1.cat_val(i, x);
    }
    pw[0] = 1, rpw[0] = 1;
    for (int i = 1; i < MAXN; i++) pw[i] = (__int128_t)pw[i - 1] * SEED % MOD;
    rseed = mpow(SEED, MOD - 2);
    for (int i = 1; i < MAXN; i++) rpw[i] = (__int128_t)rpw[i - 1] * rseed % MOD;
    SegTree1.build(1, 1, n); 

    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long v;
            cin >> v;
            SegTree1.add(1, l, r, v);
        }
        else {
            uint64_t val1 = SegTree1.query_expr(1, l, r);
            uint64_t val2 = SegTree1.query_rev(1, l, r);
            uint64_t val3 = SegTree1.query_sum(1, l, r);

            if (val3 * 2 % (r - l + 1)) {
                cout << "NO" << endl;
                continue;
            }
            __int128_t pww;
            if (val3 * 2 / (r - l + 1) < MAXN) pww = pw[val3 * 2 / (r - l + 1)];
            else pww = mpow(SEED, val3 * 2 / (r - l + 1));
            __int128_t vall = pww * (__int128_t)val2 % MOD;
            if (val1 == vall) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 7624kb

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: 0

Accepted

time: 353ms

memory: 30680kb

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:

ok 100047 token(s): yes count is 22, no count is 100025

Test #3:

score: 0

Accepted

time: 355ms

memory: 30708kb

input:

200000 200000
5 5 2 0 1 1 4 1 1 0 4 2 2 5 5 4 1 2 2 0 3 3 3 2 5 4 1 5 1 0 0 4 3 4 2 2 3 1 4 2 0 5 4 0 2 5 5 5 2 2 3 4 0 2 2 5 0 2 3 5 4 0 0 2 1 0 5 3 1 4 5 2 2 3 4 5 0 5 5 5 3 3 0 1 4 3 0 0 3 2 2 0 4 5 5 5 2 4 5 2 5 3 1 1 5 2 1 0 1 0 5 0 0 1 5 1 5 3 1 5 3 5 4 0 2 2 4 2 5 2 3 4 5 4 3 5 2 5 2 4 5 3 4 ...

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:

ok 99734 token(s): yes count is 10, no count is 99724

Test #4:

score: -100

Time Limit Exceeded

input:

200000 200000
185447 70128 80288 38126 188018 126450 46081 189881 15377 21028 12588 100061 7218 74518 162803 34448 90998 44793 167718 16370 136024 153269 186316 137564 3082 169700 175712 19214 82647 72919 170919 142138 57755 168197 81575 126456 183138 106882 167154 184388 198667 190302 188371 183732...

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
...