백준26034 Keyboard Queries

작성일 | In

문제 링크

  • https://icpc.me/26034

문제 출처

  • 2022 NCPC K번

사용 알고리즘

  • 세그먼트 트리
  • 파라메트릭 서치
  • 해싱

시간복잡도

  • $O(N \log^2 N + Q \log N)$

풀이

문자열의 특정 부분 문자열 $S[l\cdots r]$이 팰린드롬이라는 정보 몇 개만 갖고 $S[a\cdots b] = S[c\cdots d]$인지 판별하는 쿼리를 처리해야 합니다. 문자열이 같은지 판별하는 것은 해싱, 문자열의 $i$번째와 $j$번째 글자가 같다는 정보는 Union-Find로 관리하는 것이 자연스러운 발상입니다.

$S$의 부분 문자열 $S[l\cdots r]$이 팰린드롬이라는 정보가 주어지면 $Union(l,r), Union(l+1,r-1), Union(l+2,r-2), \cdots$를 수행할 것입니다. 당연히 매번 $O(N)$번의 Union 연산을 수행하면 안 되기 때문에, 파라메트릭 서치를 이용해 “아직 합쳐지지 않은 가장 바깥 문자”를 찾아서 Union할 것입니다.
파라메트릭 서치를 수행하기 위해서는 “바깥 $x$문자가 모두 동일한가?”, 즉 길이가 $x$인 접두사가 접미사를 뒤집은 것과 같은지 판별하는 결정 문제를 해결할 수 있어야 합니다. 그리고 이러한 결정 문제는 $S$ 뒤에 $S$를 뒤집어서 이어붙인 문자열을 들고 있다면 2번 쿼리와 동일한 방식으로 해결할 수 있습니다.

이제 자료구조를 구체적으로 설계해 봅시다.
문자열은 $S$ 뒤에 $S$를 뒤집은 것을 한 번 더 이어붙인 문자열을 관리할 것입니다. 문자열의 해시값을 세그먼트 트리로 관리할 것이고, 각 문자의 해시값은 Union-Find 상에서의 집합 번호입니다.
2번 쿼리는 단순히 세그먼트 트리에서 두 구간 $[a, b]$와 $[c, d]$에 쿼리를 날려서 결과물이 같은지 확인하면 됩니다. 아래 코드의 EqualRange 함수 부분입니다.
1번 쿼리는 파라메트릭 서치를 이용해 Union할 문자의 위치를 찾아서 Union하고 변경된 정보를 세그먼트 트리에 반영합니다. 파라메트릭 서치의 결정 문제에서는 접두사가 접미사를 뒤집은 것과 같은지 확인해아 하는데, 접미사를 뒤집은 것은 S를 뒤집어서 붙인 부분에서 탐색하면 2번 쿼리와 동일한 방법으로 해결할 수 있습니다. 아래 코드의 MergeRange 함수 부분입니다.

2번 쿼리는 세그먼트 트리에 쿼리를 2번 날리는 것이 전부이므로 쿼리당 $O(\log N)$입니다. 1번 쿼리에서 Union은 최대 $O(N)$번 호출되므로 결정 문제를 $O(N \log N)$번 호출하게 되고, 각 결정 문제는 2번 쿼리와 동일하게 $O(\log N)$ 시간에 해결할 수 있으므로 1번 쿼리에서 필요한 총 연산 횟수는 $O(N \log^2 N)$입니다.
따라서 전체 시간 복잡도는 $O(N \log^2 N + Q \log N)$입니다.

전체 코드

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
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1 << 18, DIM = 2;
constexpr ll Pr[DIM] = {1299709, 1301021};
constexpr ll Md[DIM] = {1'000'000'007, 1'000'000'009};
ll Pow[SZ][DIM];

struct Hash{
    array<ll, DIM+1> a;
    Hash(){ a.fill(0); }
    Hash(ll v){ a.fill(v); a.back() = 1; }
    Hash operator + (const Hash &t) const {
        Hash res = 0;
        for(int i=0; i<DIM; i++) res.a[i] = (a[i] * Pow[t.a.back()][i] + t.a[i]) % Md[i];
        res.a.back() = a.back() + t.a.back();
        return res;
    }
    bool operator == (const Hash &t) const { return a == t.a; }
};

Hash T[SZ << 1];

void Update(int x, ll v){
    x |= SZ; T[x] = Hash(v);
    while(x >>= 1) T[x] = T[x<<1] + T[x<<1|1];
}

Hash Query(int l, int r){
    l |= SZ; r |= SZ;
    Hash lv, rv;
    while(l <= r){
        if(l & 1) lv = lv + T[l++];
        if(~r & 1) rv = T[r--] + rv;
        l >>= 1; r >>= 1;
    }
    return lv + rv;
}

int N, Q, P[SZ];
vector<int> V[SZ];

int Find(int v){ return v == P[v] ? v : P[v] = Find(P[v]); }
void Merge(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v) return;
    if(V[u].size() > V[v].size()) swap(u, v);
    for(auto i : V[u]) Update(i, v), V[v].push_back(i);
    P[u] = v;
}

void Build(){
    for(int i=0; i<DIM; i++) Pow[0][i] = 1;
    for(int i=1; i<SZ; i++) for(int j=0; j<DIM; j++) Pow[i][j] = Pow[i-1][j] * Pr[j] % Md[j];
    for(int i=1; i<=N; i++) T[i+SZ] = T[N+N-i+1+SZ] = Hash(i);
    for(int i=SZ-1; i; i--) T[i] = T[i<<1] + T[i<<1|1];
    for(int i=1; i<=N; i++) P[i] = P[N+N-i+1] = i, V[i] = {i, N+N-i+1};
}

bool EqualRange(int a, int b, int len){
    return Query(a, a+len-1) == Query(b, b+len-1);
}

void MergeRange(int a, int b, int len){
    while(len > 0 && !EqualRange(a, b, len)){
        int l = 1, r = len;
        while(l < r){
            int m = (l + r) / 2;
            if(!EqualRange(a, b, len)) r = m;
            else l = m + 1;
        }
        Merge(a+r-1, b+r-1);
        a += r; b += r; len -= r;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q; Build();
    for(int i=1; i<=Q; i++){
        int op; cin >> op;
        if(op == 1){
            int a, b; cin >> a >> b;
            MergeRange(a, N+N-b+1, b-a+1);
        }
        if(op == 2){
            int a, b, c, d; cin >> a >> b >> c >> d;
            if(b - a != d - c) cout << "Not equal\n";
            else if(EqualRange(a, c, b-a+1)) cout << "Equal\n";
            else cout << "Unknown\n";
        }
    }
}