백준20193 화려한 정사각형

작성일 | In

문제 링크

  • http://icpc.me/20193

문제 출처

  • 2020 KOI 고등부 3번

사용 알고리즘

  • 세그먼트 트리
  • 스위핑

시간복잡도

  • $O(N \log N \log X)$

풀이

최소 길이를 구하는 문제이므로 파라메트릭 서치를 생각해볼 수 있습니다.
$decision(R) := $ 길이가 $R$인 정사각형으로 $K$가지의 색을 모두 덮을 수 있는가? 라는 결정 문제를 $O(\log X)$번 해결하는 것으로 문제의 답을 구할 수 있습니다. 결정 문제를 푸는 방법을 알아봅시다.

$[X, X+R]$ 구간을 왼쪽에서 오른쪽으로 움직이면서 스위핑을 합시다. 점 $(x_i, y_i, k_i)$는 $X = x_i-R$ 시점(구간의 오른쪽 끝과 만나는 시점)에 구간에 들어가고, $X = x_i+1$ 시점(구간의 왼쪽 끝보다 작아지는 시점)에 구간에서 빠져나옵니다.
만약 모든 점들의 색깔이 다르다면, Segment Tree + Lazy Propagation을 이용해 점 $(x_i, y_i, k_i)$가 구간에 들어갈 때 $[y_i, y_i + R]$을 1만큼 증가시키고, 구간에서 빠져나올 때 $[y_i, y_i + R]$을 1만큼 감소시키면서, 최댓값이 $K$인 순간이 있는지 확인해주면 됩니다. 그러나 이 문제에서는 서로 같은 색깔을 가진 점들이 존재할 수 있습니다. 이런 경우는 어떻게 처리해야 할까요?

위에서 설명한 알고리즘은 똑같은 색깔에 대해 중복해서 값을 증가/감소시키는 경우가 발생하기 때문에 문제가 됩니다. 중복해서 값을 증가/감소시키는 것을 피하는 방법을 찾으면 됩니다.
현재 구간에 들어간 점들의 $y$좌표를 색깔별로 구분하여 저장합시다.
점 $(x_i, y_i, k_i)$가 구간에 들어갈 때는 이미 구간에 있는 색깔이 $k_i$인 점들 중 ($y_i$ 이하이면서 가장 큰 점)/($y_i$ 이상이면서 가장 작은 점)의 위치를 찾아서 그 사이 구간만 1 증가시키면 됩니다.
마찬가지로, 점 $(x_i, y_i, k_i)$가 구간에서 빠져나올 때는 구간에 있는 색깔이 $k_i$이고 현재 제거하는 점이 아닌 점들 중 ($y_i$ 이하이면서 가장 큰 점)/($y_i$ 이상이면서 가장 작은 점)의 위치를 찾아서 그 사이 구간만 1 감소시키면 됩니다.

어떤 수 이하이면서 가장 큰 수 / 이상이면서 가장 작은 수는 std::multiset을 이용해 $O(\log N)$만에 찾을 수 있습니다. 또한 Segment Tree + Lazy Propagation을 이용해 구간의 값을 증가시키는 것과 최댓값을 구하는 것도 $O(\log N)$만에 수행할 수 있습니다.
결정 문제마다 이 작업을 $2N$번씩 수행하고, 이러한 결정 문제를 총 $O(\log X)$번 풀기 때문에 전체 시간 복잡도는 $O(N \log N \log X)$가 됩니다.

전체 코드

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
constexpr int S = 1 << 18;

struct Event{
    int op, x, y, c;
    Event() = default;
    Event(int op, int x, int y, int c) : op(op), x(x), y(y), c(c) {}
    bool operator < (const Event &e) { return tie(x, op) < tie(e.x, e.op); }
};

struct SegmentTree{
    int T[S << 1], L[S << 1];
    void clear(){ memset(T, 0, sizeof T); memset(L, 0, sizeof L); }
    void push(int node, int s, int e){
        T[node] += L[node];
        if(s != e) for(auto c : {node<<1, node<<1|1}) L[c] += L[node];
        L[node] = 0;
    }
    void update(int l, int r, int v, int node=1, int s=0, int e=S-1){
        push(node, s, e);
        if(r < s || e < l) return;
        if(l <= s && e <= r){ L[node] += v; push(node, s, e); return; }
        int m = s + e >> 1;
        update(l, r, v, node<<1, s, m);
        update(l, r, v, node<<1|1, m+1, e);
        T[node] = max(T[node<<1], T[node<<1|1]);
    }
    int query(){ push(1, 0, S-1); return T[1]; }
} Seg;

int N, K, X[101010], Y[101010], C[101010];
vector<Event> events;
multiset<int> st[252525];

bool Check(int R){
    Seg.clear();
    for(int i=1; i<=K; i++) st[i] = multiset<int>{0, S-1};
    events.clear();
    for(int i=1; i<=N; i++){
        events.emplace_back(+1, X[i], Y[i], C[i]);
        events.emplace_back(-1, X[i]+R, Y[i], C[i]);
    }
    sort(all(events));

    for(const auto &[op, x, y, c] : events){
        if(op == -1){
            auto it = st[c].lower_bound(y);
            int l = max(y, *prev(it) + R);
            int r = min(y + R, *next(it));
            Seg.update(l, r-1, -1);
            st[c].erase(it);
        }
        else{
            auto it = st[c].insert(y);
            int l = max(y, *prev(it) + R);
            int r = min(y + R, *next(it));
            Seg.update(l, r-1, +1);
            if(Seg.query() == K) return true;
        }
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> X[i] >> Y[i] >> C[i];

    events.reserve(N+N);
    int l = 1, r = 252525;
    while(l < r){
        int m = l + r >> 1;
        if(Check(m)) r = m;
        else l = m + 1;
    }
    cout << r - 1;
}