백준11840 XOR

작성일 | In

문제 링크

  • http://icpc.me/11840

사용 알고리즘

  • Persistent Trie

풀이

먼저 Prefix XOR을 만듭시다. $A_e \oplus A_{s-1} \geq K$를 만족하는 가장 긴 구간 $[s, e]$를 찾아야 하고, 이는 각각의 $e$마다 $A_e \oplus A_{s-1} \geq K$인 가장 작은 $s$를 찾는 것으로 해결할 수 있습니다.
파라메트릭 서치를 합시다. 구체적으로, $\max\left{ A_e \oplus A_1, A_e \oplus A_2, \cdots, A_e \oplus A_m \right} \geq K$인 가장 작은 $m$을 찾을 것입니다. $\left{ A_1, A_2, \cdots, A_m \right}$를 저장한 Trie가 있다면 결정 문제를 $O(\log X)$ 시간에 해결할 수 있습니다.

하지만 Trie를 $O(N)$개 만드는 것은 불가능하기 때문에 더 효율적인 방법을 생각해야 합니다.
여러가지 방법이 있겠지만, 가장 간단한 방법은 persistent trie를 만드는 것입니다. persistent segment tree와 비슷하게, 원소 하나를 삽입할 때 변경되는 $O(\log X)$개의 정점만 새로 생성하는 것입니다. 시간 복잡도와 공간 복잡도 모두 일반적인 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
#include <bits/stdc++.h>
using namespace std;

struct Trie{
    Trie *c[2]; int sz;
    Trie(){ c[0] = c[1] = nullptr; sz = 0; }
};

void Insert(Trie *prv, Trie *now, int v, int d=29){
    if(d == -1) return;
    int key = v >> d & 1;
    if(!now->c[key] || prv && now->c[key] == prv->c[key]) now->c[key] = new Trie;
    if(!now->c[!key] && prv) now->c[!key] = prv->c[!key];
    Insert(prv ? prv->c[key] : nullptr, now->c[key], v, d-1);
}

int Query(Trie *now, int v, int d=29){
    if(d == -1) return 0;
    int key = v >> d & 1;
    if(now->c[!key]) return Query(now->c[!key], v, d-1) | (1 << d);
    else return Query(now->c[key], v, d-1);
}

int N, K, A[252525], L[252525];
Trie *T[252525], *Base;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> A[i], A[i] ^= A[i-1];
    Base = new Trie;
    for(int i=0; i<=N; i++){
        T[i] = new Trie;
        Insert(i ? T[i-1] : Base, T[i], A[i]);
    }

    for(int i=1; i<=N; i++){
        if(Query(T[i-1], A[i]) < K){ L[i] = 1e9; continue; }
        int l = 0, r = i - 1;
        while(l < r){
            int m = (l + r) / 2;
            if(Query(T[m], A[i]) >= K) r = m;
            else l = m + 1;
        }
        L[i] = r;
    }

    int mx = 0, st = -1;
    for(int i=1; i<=N; i++){
        int len = i - L[i], now = L[i] + 1;
        if(len > mx || len == mx && now < st) mx = len, st = now;
    }
    cout << st << " " << mx << "\n";
}