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}$,歡迎追蹤!
留言
張貼留言