QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1021#644282#9302. Caesar Ciphership2077castcSuccess!2024-10-21 09:39:322024-10-21 09:39:32

Details

Extra Test:

Wrong Answer
time: 3ms
memory: 7756kb

input:

41 1
0 15 15 15 31 34 41 41 41 41 41 41 41 43 43 43 43 63 67 67 65469 0 0 4 24 24 24 24 26 26 26 26 26 26 26 33 36 52 52 52 67
2 1 22 20

output:

yes

result:

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

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644282#9302. Caesar CiphercastcWA 1335ms87276kbC++205.3kb2024-10-16 12:44:262024-10-21 09:40:14

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define int long long
template<class Info, class Tag>
struct LazySegmentTree {
    const int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree(int n) : n(n), info(4 << __lg(n)), tag(4 << __lg(n)) {}
    LazySegmentTree(vector<Info> init) : LazySegmentTree(init.size()) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 0, n - 1);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n - 1, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        if(l > r) return Info();
        return rangeQuery(1, 0, n - 1, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n - 1, l, r, v);
    }
    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, {-(info[p].min + 1) / 2});
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m + 1, r);
        pull(p);
    }
    void half() {
        half(1, 0, n - 1);
    }
};
const int mod = 1247493647;
const int P = 65536;
const int N = 5e5 + 9;
int pw[N];
struct Tag {
    ll add = 0;
    
    void apply(Tag t) {
        add += t.add;
    }
};

struct Info {
    int ans = 0, add = 0, g = 0, sum = 0;
    
    void apply(Tag t) {
        ans += t.add * add % mod;
        sum += t.add * g;
    }
};

Info operator+(Info a, Info b) {
    Info c;
    if(a.add == 0) return b;
    if(b.add == 0) return a;    
    c.sum = (a.sum + b.sum) % P;
    c.ans = (a.ans * pw[b.g] + b.ans) % mod;
    c.add = (a.add * pw[b.g] + b.add) % mod;
    c.g = a.g + b.g;
    return c;
}
void solve() {
    pw[0] = 1;
    for(int i = 1; i < N; i++) {
        pw[i] = pw[i - 1] * 131;
        pw[i] %= mod;
    }
    int n, q;
    cin >> n >> q;
    vector<Info> init(n);
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        init[i].add = 1;
        init[i].g = 1;
    } 
    for(int i = 0; i < n; i++) {
        if(i == 0) b[i] = a[i];
        else b[i] = a[i] - a[i - 1];
        b[i] += P;
        b[i] %= P;
        init[i].sum = init[i].ans = b[i];
    }
    LazySegmentTree<Info, Tag> seg(init);
    while(q--) {
        int op;
        cin >> op;
        if(op == 1) {
            int l, r;
            cin >> l >> r;
            l--;
            auto p = seg.rangeQuery(l, l);
            p.ans++;
            p.ans %= P;
            p.sum = p.ans;
            seg.modify(l, p);
            if(r < n) {
                p = seg.rangeQuery(r, r);
                p.ans--;
                p.ans += P;
                p.ans %= P;
                p.sum = p.ans;
                seg.modify(r, p);
            }
        } else {
            int x, y, L;
            cin >> x >> y >> L;
            x--, y--;
            int flag = seg.rangeQuery(x + 1, x + L - 1).ans;
            flag -= seg.rangeQuery(y + 1, y + L - 1).ans;
            if(flag != 0) {
                cout << "no\n";
            } else {
                if(seg.rangeQuery(0, x).sum == seg.rangeQuery(0, y).sum) {
                    cout << "yes\n";
                } else {
                    cout << "no\n";
                }
            }
        }
    }
}          
    
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    // cin >> T;
    while(T--) solve();

    return 0;
}