算法竞赛模板

2025 吉林省赛 H

线段树 + 哈希
奇偶分别维护哈希值 $ base^k $
如果区间同时增加$ x $, 相当于整个区间乘$ base ^ x $
时间复杂度 $ 𝑂(𝑛 + 𝑞 log 𝑛) $

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int base = 1331;

int ksm(int a, int b) {
    int ans = 1;
    while (b > 0) {
        if (b % 2) ans = (ans * a);
        a = (a * a);
        b >>= 1;
    }
    return ans;
} 


struct node {
    int suma, sumb; // suma: 奇数位置的和, sumb: 偶数位置的和
    node() : suma(0), sumb(0) {}
    void apply(int T) {
        suma *= T;
        sumb *= T;
    }
    node operator+ (const node& b) const {
        node t;
        t.suma = suma + b.suma;
        t.sumb = sumb + b.sumb;
        return t;
    }
};

struct lazy {
    int n;
    vector<node> tree;
    vector<int> tg;
    lazy(int _n, vector<node>& b) : n(_n) {
        tree.assign(4 * n, node());
        tg.assign(4 * n, 1);
        auto bd = [&] (auto&& self, int l, int r, int p) -> void {
            if (l == r) {
                tree[p] = b[l];
                return;
            }
            int mid = l + r >> 1;
            self(self,l, mid, p << 1);
            self(self,mid + 1, r, p << 1 | 1);
            up(p);
        };
        bd(bd,1,n,1);
    }

    void up(int p) {
        tree[p] = tree[p << 1] + tree[p << 1 | 1];
    }

    void apply(int p, int T) {
        tree[p].apply(T);
        tg[p] *= T;
    }

    void down(int p) {
        apply(p << 1, tg[p]);
        apply(p << 1 | 1, tg[p]);
        tg[p] = 1; // 2^0 = 1
    }

    void modify(int ml, int mr, int l, int r, int p, int T) {
        if (r < ml || l > mr) return;
        if (l >= ml && r <= mr) {
            apply(p, T);
            return;
        }
        int mid = l + r >> 1;
        down(p);
        modify(ml, mr, l, mid, p << 1, T);
        modify(ml, mr, mid + 1, r, p << 1 | 1, T);
        up(p);
    }

    void modify(int l, int r, int T) {
        modify(l, r, 1, n, 1, T);
    }

    node query(int ql, int qr, int l, int r, int p) {
        if (l >= ql && r <= qr) {
            return tree[p];
        }
        int mid = l + r >> 1;
        down(p);
        if (qr <= mid) {
            return query(ql, qr, l, mid, p << 1);
        } else if (ql > mid) {
            return query(ql, qr, mid + 1, r, p << 1 | 1);
        } else {
            return query(ql, qr, l, mid, p << 1) + 
                   query(ql, qr, mid + 1, r, p << 1 | 1);
        }
    }

    node query(int l, int r) {
        return query(l, r, 1, n, 1);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<node> a(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (i % 2 == 1) {
            a[i].suma = ksm(base, x);
            a[i].sumb = 0;
        } else {
            a[i].sumb = ksm(base, x);
            a[i].suma = 0;
        }
    }
    lazy tree(n, a);
    while (q--) {
        int op, l, r, v;
        cin >> op >> l >> r;
        if (op == 0) {
            cin >> v;
            v = ksm(base,v);
            tree.modify(l, r, v);
        } else {
            node res = tree.query(l, r);
            if (res.suma == res.sumb) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
    return 0;
}

多重集合判断相等，用和哈希 + ull自然溢出
性能好，几乎不会被卡

如果要修改，还不能这样用因为 ha(y) + ha(x) != ha(x+y)

Rearrange Query

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
static mt19937_64 rng(random_device{}());
const int N = 2e5 + 10;
int ha[N], a[N], b[N];
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        ha[i] = rng();
        // cout << ha[i] << endl;
    }
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a[i] = ha[x];
    }
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        b[i] = ha[x];
    }
    for (int i = 1; i <= n; i++) {
        a[i] += a[i-1];
        b[i] += b[i-1];
    }
    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (a[r1] - a[l1-1] == b[r2] - b[l2-1]) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }
    }
    return 0;
}