[백준 20193] 화려한 직사각형

이런 류의 문제는 처음 접근 해본다. 되게 오랫동안 고민했으며, 이런 유형의 문제에 되게 약하다는 것을 알게 되었다.

1. 아이디어

 

얼추 생각나는 풀이는 어떤 \(x\)좌표 \(2\)개를 잡아 그 사이의 간격을 \(dx\)라고 하고, 그 사이의 각 점, 어떤 \(y\)에 대해서 \([y-dx, y]\)이 구간안에 다른 모든 색깔이 포함되는 \(y\)가 존재하는 지 판별하면 어떨까 생각했다.

 

 

하지만 어떤 \(x\)좌표를 \(2\)개를 잡는 다는 것은 \(O(N^2)\)개의 구간이 나오기 때문에 이분탐색 아이디어를 적용시켜야된다.

어떤 \(x\)구간을 \([x-R, x]\)라고 두고, \(R\)에 대해 이분탐색을 하고, \(f(R)\) 어떤 \(R\)이하의 화려한 직사각형이 존재하는 가로 변형시켜 이분탐색을 진행한다.

2. f(R) 정의하기

다음으로 구간안에서 "어떤 \(y\)에 대해서 \([y-dx, y]\) 이 구간안에 다른 모든 색깔이 포함되는 \(y\)가 존재하는 지 판별"하는 함수 \(f(R)\)를 만들어야 된다.

 

간단한 아이디어로 \([x-R, x]\)에 있는 점\((x, y)\)에 대해 \([y-dx, y]\)에 \(1\)을 더해준다. 이때 주의할 점이 같은 색깔의 점이 겹치지 않게 더해주어야 한다.

 

 

그렇다면 \([y-dx, y]\)에는 서로 다른 색깔들의 점들의 구간이 몇개 겹쳐있는 지를 알 수 있고, 이중 최대값이 \(k\)라면 \(f(R)\)이 가능하다는 소리이다.

구간을 더해주는 연산은 lazy segment tree로 해결하면 된다.

위의 사진에서 \([1, A], [1, C]\)가 이미 더해져있다고 가정하고, \([1, B]\)가 어떻게 구간이 업데이트 되는지 보자

 

어떤 구간 \([a, b]\)를 업데이트를 해야되고 \(a=y-dx, b = y\) 이다.

 

 

$$ a = max(y - dx, (자신과\;같은\;색깔이고\;자신의\;y좌표\;바로\;아래에\;있는\;y좌표) + 1) $$

 

$$ b = min(y, (자신과\;같은\;색깔이고\;자신의\;y좌표\;바로\;위에\;있는\;y좌표) - dx - 1) $$

 

 

으로 정의할 수 있다. 따라서 \([1, B]\)는 구간 \([2, 1]\)을 더해야 되고, 이 구간을 어긋나있으므로 업데이트를 하지 않는다.

자신의 \(y\)좌표 바로 아래 혹은 위에 있는 좌표는 multiset으로 관리해주면 \(logn\)에 구해줄 수 있다.

3.시간복잡도

 

각 \([x-R, x]\)구간에 있는 점들을 관리하는 것은 deque로 스위핑하듯이 구할 수 있으며, 구간에서 나가는 점에대해서는 구간 \([a, b]\)에 \(-1\)을 더해주면 되고, 구간에 들어오는 점에 대해서는 구간\([a, b] 1\)을 더해주면 된다.

 

 

 

\(x\)의 후보는 각 점들을 좌표압축을 한 것이고, 그 \(x\)좌표는 \(O(N)\)개가 존재한다. 또한 lazy segment tree를 통해 최대 \(N\)번 업데이트를 하니깐 \(f(R)\)의 최종 시간 복잡도는 \(O(NlogX)\)이다. (\(X\)는 최대 좌표, 최대 \(250000\))

 

 

또한 \(R\)에 대해서는 \([0, X]\)에서 이분탐색을 하므로 최종 시간 복잡도는 \(O(Nlog^2X)\)가 된다.

4. 소스코드

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> pi;
 
struct Vertex {
    int x, y, color;
};
struct cmp {
    bool operator()(const Vertex& v1, const Vertex& v2) const {
        if (v1.y != v2.y) return v1.y < v2.y;
        return v1.x < v2.x;
    };
};
 
struct Segment {
    int n;
    vector<int> seg, lazy;
    void Init(int _n) {
        n = _n;
        seg.clear(), lazy.clear();
        seg.resize(4 * n), lazy.resize(4*n);
    }
 
    void updatelazy(int num, int s, int e) {
        if (lazy[num] == 0) return;
        seg[num] += lazy[num];
        if (s != e) {
            lazy[2 * num] += lazy[num];
            lazy[2 * num+1] += lazy[num];
        }
        lazy[num] = 0;
    }
    int update(int num, int s, int e, int l, int r, int diff) {
        updatelazy(num, s, e);
        if (r < s || e < l) return seg[num];
        if (l <= s && e <= r) {
            seg[num] += diff;
            if (s != e) {
                lazy[2 * num] += diff;
                lazy[2 * num+1] += diff;
            }
            return seg[num];
        }
 
        int mid = s + e >> 1;
        return seg[num] = max(
            update(2*num, s, mid, l, r, diff), update(2*num+1, mid+1,e, l, r, diff));
    }
    void update(int l, int r, int diff) { update(1, 0, n - 1, l, r, diff); }
 
    int query(int num, int s, int e, int l, int r) {
        updatelazy(num, s, e);
        if (r < s || e < l) return 0;
        if (l <= s && e <= r) return seg[num];
 
        int mid = s + e >> 1;
        return max(query(2*num, s, mid, l, r), query(2*num+1, mid+1, e, l, r));
    }
    int query(int l, int r) { return query(1, 0, n-1, l, r); }
}tree;
 
int n, k;
vector<Vertex> arr;
 
set<int> sx;
vector<Vertex> Xpos[250001];
 
vector<multiset<Vertex, cmp>> col;
 
pi getRange(multiset<Vertex, cmp>::iterator itr, int mid) {
    Vertex v = *itr;
 
    int s = v.y, e = v.y - mid;
    if (next(itr) != col[v.color].end()) {
        auto nxt = next(itr);
        if (nxt->y - mid <= s) s = nxt->y - mid-1;
    }
    if (itr != col[v.color].begin()) {
        auto prv = prev(itr);
        if (v.y - mid <= prv->y) e = prv->y+1;
    }
 
    return { e, s };
}
 
bool f(int mid) {
    tree.Init(250001);
 
    col.clear(); col.resize(k+1);
 
    deque<Vertex> dq;
    for (int x : sx) {
        while (!dq.empty() && dq.front().x < x - mid) {
            Vertex& v = dq.front();
            auto pos = col[v.color].find(v);
 
            pi range = getRange(pos, mid);
            if(range.first <= range.second)
                tree.update(max(0, range.first), range.second, -1);
            col[v.color].erase(pos);
 
            dq.pop_front();
        }
 
        for (Vertex& v : Xpos[x]) {
            auto pos = col[v.color].insert(v);
 
            pi range = getRange(pos, mid);
            if(range.first <= range.second)
                tree.update(max(0, range.first), range.second, 1);
            dq.push_back(v);
        }
 
        if (tree.query(0, 250000) == k) return true;
    }
 
    return false;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i].x >> arr[i].y >> arr[i].color;
        sx.insert(arr[i].x);
    }
 
    sort(arr.begin(), arr.end(), [](const Vertex& v1, const Vertex& v2) -> bool {
        if (v1.x != v2.x) return v1.x < v2.x;
        return v1.y < v2.y;
        });
    for (Vertex& v : arr)
        Xpos[v.x].push_back(v);
 
    int lo = 0, hi = 250000;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (f(mid)) hi = mid - 1;
        else lo = mid + 1;
    }
 
    cout << lo;
 
    return 0;
}