TIOJ 1920：植物大戰殭屍

TIOJ 1920：植物大戰殭屍

題目大意：給陣列 $a[n]$，每筆詢問給 $l, r, v$，找出一個 $k$，$l ≤ k < r$，$a[k] ⊕ a[k+1] ⊕...⊕ a[r - 1] ⊕ v$ 為最大值。

解法：可以離線處理，使用 $trie$ 從最大位元找，並記錄此位元最小出現的位置。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(x,a,b) for(int x=a;x<=b;x++)

const int SIZE = 1e4 + 5, QSIZE = 1e6 + 5;

int cnt = 1, to[30 * SIZE][2], mp[30 * SIZE];

void update (int x, int p) {
    int node = 1;
    for (int i = 29; i >= 0; i--) {
        bool b = (x >> i) & 1;
        if (!to[node][b])
            to[node][b] = ++cnt, mp[cnt] = 2e9;
        node = to[node][b];
        mp[node] = min (mp[node], p);
    }
}

int query (int x, int p) {
    int node = 1, re = 0;
    for (int i = 29; i >= 0; i--) {
        bool b = (x >> i) & 1;
        if (!to[node][b ^ 1] || mp[to[node][b ^ 1]] > p)
            b ^= 1;
        (re <<= 1) |= b ^ 1;
        node = to[node][b ^ 1];
    }
    return re;
}

struct Ask {
    int id, l, r, v;
    Ask() {}
    Ask (int id, int l, int r, int v) : id (id), l (l), r (r), v (v) {}
    bool operator < (const Ask &a) const {
        return l > a.l;
    }
} ask[QSIZE];

int n, q, a[SIZE], ans[QSIZE];

void solve() {
    cin >> n >> q;
    a[0] = 0;
    FOR (i, 1, n) cin >> a[i], a[i] ^= a[i - 1];
    FOR (i, 1, q) {
        int l, r, v;
        cin >> l >> r >> v;
        ask[i] = {i, l + 1, r, v};
    }
    sort (ask + 1, ask + q + 1);

    int nl = n + 1;
    FOR (i, 1, q) {
        int l = ask[i].l, r = ask[i].r, v = ask[i].v;
        while (nl >= l)
            nl--, update (a[nl], nl);
        ans[ask[i].id] = a[r] ^ v ^ query (a[r] ^ v, r - 1);
    }
    FOR (i, 1, q) cout << ans[i] << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！