QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1604#931258#9774. Same SumwallcrackLyc-123Failed.2025-03-19 15:39:422025-03-19 15:39:43

详细

Extra Test:

Invalid Input

input:

10 10
0 4 0 2 1 7 7 2 8 0
1 1 5 5
1 9 9 5
2 1 4
2 4 10
2 8 10
1 7 10 5
2 3 5
2 9 10
2 10 10
2 1 3

output:


result:

FAIL not even

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#931258#9774. Same SumLyc-123AC ✓471ms39172kbC++205.9kb2025-03-10 22:07:022025-03-10 22:07:03

answer

#include <bits/stdc++.h>
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;
        uint64_t tge;
        uint64_t tgn;
    } a[4 * MAXN];
    int val[MAXN];
    uint64_t seed;
public:
    SegmentTree() {
        seed = SEED;
    }
    void cat_val(int i, uint64_t x) { val[i] = x; }
    void build(int u, int l, int r) {
        a[u].l = l, a[u].r = r;
        a[u].tag = 0;
        a[u].tge = a[u].tgn = 1;
        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].l == a[u].r) return;
        if (a[u].tag) {
            a[u << 1].tag += a[u].tag;
            a[u << 1 | 1].tag += a[u].tag;
            a[u << 1].sum += (__int128_t)a[u].tag * (a[u << 1].r - a[u << 1].l + 1);
            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;
        }
        if (a[u].tge != 1) {
            a[u << 1].tge = (__int128_t)a[u << 1].tge * a[u].tge % MOD;
            a[u << 1 | 1].tge = (__int128_t)a[u << 1 | 1].tge * a[u].tge % MOD;
            a[u << 1].expr = (__int128_t)a[u << 1].expr * a[u].tge % MOD;
            a[u << 1 | 1].expr = (__int128_t)a[u << 1 | 1].expr * a[u].tge % MOD;
            a[u].tge = 1;
        } 
        if (a[u].tgn != 1) {
            a[u << 1].tgn = (__int128_t)a[u << 1].tgn * a[u].tgn % MOD;
            a[u << 1 | 1].tgn = (__int128_t)a[u << 1 | 1].tgn * a[u].tgn % MOD;
            a[u << 1].rev = (__int128_t)a[u << 1].rev * a[u].tgn % MOD;
            a[u << 1 | 1].rev = (__int128_t)a[u << 1 | 1].rev * a[u].tgn % MOD;
            a[u].tgn = 1;

        }
    }
    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;
            a[u].tge = (__int128_t)a[u].tge * pw[w] % MOD;
            a[u].tgn = (__int128_t)a[u].tgn * rpw[w] % MOD;
            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;
}