TIOJ 1920

Created2021-03-14Updated2021-03-14

連結

題意

給定一個長度nn的陣列，有qq筆詢問，每筆詢問給定l,r,vl, r, v
請找出l≤k<rl \leq k < r，區間[k,r)[k, r)和vv的xor最大值

1≤n≤104,1≤q≤106,0≤C<2301 \leq n \leq 10^4, 1 \leq q \leq 10^6, 0 \leq C < 2^{30}

解法

首先，假設算好suf[i]suf[i]代表後綴[i,n)[i, n)的xor值
由xor的性質推出答案 = suf[k]⊕suf[r]⊕vsuf[k] \oplus suf[r] \oplus v
那問題就回到要如何找出最好的kk使那串數最大

再來思考一個較單純的問題，給定一個陣列a，有qq筆詢問
每筆詢問給定一個數xx，求ai⊕xa_i \oplus x的最大值
作法就是蓋一棵01-trie，先把陣列所有數字丟進trie裡
由於二進位的性質可以讓我們greedy取，假如最大位能夠出現1，就讓trie往那裡走

接下來要如何處理區間的問題
考慮一下持久化吧
存下每一個後綴的01-trie版本，並維護size
這樣在詢問的時候就能夠把兩棵trie取出來，利用size決定能不能往下走
最後決定出最大的答案

複雜度：O(qlogC)\mathcal{O}(qlogC)

code

第一次把持久化套在trie上，覺得很酷> <

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 10000, K = 111;

int dep = 29;

struct trie {
    static trie mem[N * 60], *pt;
    int sz;
    trie* ch[2];
    trie() : sz(0), ch{NULL, NULL} {}
    trie(trie *rt) : sz(rt->sz), ch{rt->ch[0], rt->ch[1]} {}
    trie* insert(int v, int d = dep) {
        trie *rt = new (pt++) trie(*this);
        rt->sz++;
        if (d < 0) return rt;
        int f = v >> d & 1;
        if (!rt->ch[f]) rt->ch[f] = new (pt++) trie();
        rt->ch[f] = rt->ch[f]->insert(v, d - 1);
        return rt;
    }
} trie::mem[N * 60], *trie::pt = mem;

int get_sz(trie *t) {return t ? t->sz : 0;}

int query(trie* l, trie* r, int v, int d = dep) {
    if (d < 0) return 0;
    int f = v >> d & 1 ^ 1;
    if ((l ? get_sz(l->ch[f]) : 0) == (r ? get_sz(r->ch[f]) : 0)) {
        return query((l ? l->ch[f ^ 1] : NULL), (r ? r->ch[f ^ 1] : NULL), v, d - 1);
    } else {
        return query((l ? l->ch[f] : NULL), (r ? r->ch[f] : NULL), v, d - 1) | (1 << d);
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector <int> pre = {0};
    vector <trie*> roots;
    trie *rt = new trie();
    rt = rt->insert(0);
    roots.pb(rt);
    for (int i = n - 1; ~i; --i) {
        pre.pb(pre.back() ^ a[i]);
        roots.pb(roots.back()->insert(pre.back()));
    }
    reverse(all(pre));
    reverse(all(roots));
    while (q--) {
        int l, r, v;
        cin >> l >> r >> v;
        cout << query(roots[l], roots[r], v ^ pre[r]) << '\n';
    }
}