QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1302#827225#9774. Same Sumship2077TJUHuangTaoSuccess!2024-12-23 09:57:512024-12-23 09:57:52

详细

Extra Test:

Wrong Answer
time: 1ms
memory: 5980kb

input:

516 1
19880 11583 24563 143974 13998 19560 4946 161496 788 17549 10796 170867 3127 22383 19641 154849 4949 5405 12570 177076 16164 14239 15785 153812 20820 10913 7778 160489 3432 15965 7345 173258 4949 5405 12570 177076 18576 10700 24075 146649 2135 16582 13069 168214 20482 19807 5117 154594 20596 2...

output:

YES

result:

wrong answer expected NO, found YES [1st token]

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#827225#9774. Same SumTJUHuangTaoWA 761ms57904kbC++233.7kb2024-12-22 20:33:132024-12-23 10:07:07

answer

#include <bits/stdc++.h>
#define int __int128_t
#define ll __int128_t
#define db double
#define pii pair<int, int>
using namespace std;
const int maxn = 2e5 + 10;
const int mod = (long long)1e18 + 201, base = 2333;
long long arr[maxn];
int ksm(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)
            res = res * a % mod;
    return res;
}
struct Node {
    ll laz1 = 0, laz2 = 0, laz3 = 0, sum = 0, pos = 0, neg = 0;
};
struct SEG {
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
    Node t[maxn << 2];
    void push_up(int rt) {
        t[rt].sum = t[ls].sum + t[rs].sum;
        t[rt].pos = (t[ls].pos + t[rs].pos) % mod;
        t[rt].neg = (t[ls].neg + t[rs].neg) % mod;
    }
    void fun(int rt, int l, int r, int k, int pos, int neg) {
        t[rt].sum += (r - l + 1) * k;
        t[rt].pos = (t[rt].pos * pos) % mod;
        t[rt].neg = (t[rt].neg * neg) % mod;
        t[rt].laz1 += k;
        t[rt].laz2 = t[rt].laz2 * pos % mod;
        t[rt].laz3 = t[rt].laz3 * neg % mod;
    }
    void push_down(int rt, int l, int r) {
        if (t[rt].laz1) {
            fun(ls, l, mid, t[rt].laz1, t[rt].laz2, t[rt].laz3);
            fun(rs, mid + 1, r, t[rt].laz1, t[rt].laz2, t[rt].laz3);
            t[rt].laz1 = 0;
            t[rt].laz2 = t[rt].laz3 = 1;
        }
    }
    void build(int rt, int l, int r) {
        t[rt].laz2 = t[rt].laz3 = 1;
        if (l == r) {
            t[rt].sum = arr[l];
            t[rt].pos = ksm(base, arr[l]);
            t[rt].neg = ksm(ksm(base, arr[l]), mod - 2);
            return;
        }
        build(ls, l, mid), build(rs, mid + 1, r);
        push_up(rt);
    }
    void update(int rt, int l, int r, int p, int q, int k, int pos, int neg) {
        if (p > r || q < l)
            return;
        if (p <= l && r <= q) {
            fun(rt, l, r, k, pos, neg);
            return;
        }
        push_down(rt, l, r);
        update(ls, l, mid, p, q, k, pos, neg),
            update(rs, mid + 1, r, p, q, k, pos, neg);
        push_up(rt);
    }
    Node query(int rt, int l, int r, int p, int q) {
        if (p <= l && r <= q)
            return t[rt];
        push_down(rt, l, r);
        if (q <= mid)
            return query(ls, l, mid, p, q);
        if (p > mid)
            return query(rs, mid + 1, r, p, q);
        Node left = query(ls, l, mid, p, mid),
             right = query(rs, mid + 1, r, mid + 1, q);
        Node res;
        res.pos = (left.pos + right.pos) % mod;
        res.neg = (left.neg + right.neg) % mod;
        res.sum = (left.sum + right.sum);
        return res;
    }
} seg;
void solve() {
    long long n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];  //, arr[i] *= 2;
    seg.build(1, 1, n);
    while (q--) {
        long long op;
        cin >> op;
        if (op == 1) {
            long long l, r, v;
            cin >> l >> r >> v;
            // v *= 2;
            seg.update(1, 1, n, l, r, v, ksm(base, v),
                       ksm(ksm(base, v), mod - 2));
        } else {
            long long l, r;
            cin >> l >> r;
            Node tem = seg.query(1, 1, n, l, r);
            if (tem.sum % ((r - l + 1) / 2)) {
                cout << "NO\n";
                continue;
            }
            int avg = 2 * tem.sum / (r - l + 1);
            if (tem.neg * ksm(base, avg) % mod == tem.pos % mod)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}