백준2601 도서실카펫

작성일 | In

문제 링크

  • https://icpc.me/2601

문제 출처

  • 2004 KOI 중등 3번

사용 알고리즘

  • 스위핑
  • 세그먼트 트리

시간복잡도

  • $O(N \log N)$

풀이

직사각형 $[x_1,x_2]\times[y_1,y_2]$가 정사각형 $[x-k,x]\times[y-k,y]$으로 가려질 조건은 다음과 같습니다.

  • $x-k \leq x_1 \leq x_2 \leq x$
  • $y-k \leq y_1 \leq y_2 \leq y$

이런 상황에서 문제를 풀 때는 최대한 적은 개수의 변수에 대한 식으로 조건을 표현하는 것이 좋습니다. 그러므로 두 부등식을 각각 $x, y$의 구간 형태로 나타내어 봅시다.

  • $x_2 \leq x \leq x_1+k$
  • $y_2 \leq y \leq y_1+k$

카펫을 적당히 배치했을 때 가릴 수 있는 직사각형의 최대 개수를 구해야 합니다. 이 문제는 직사각형마다 2차원 배열의 $[x_2,x_1+k]\times[y_2,y_1+k]$ 구간에 1을 더한 다음, 배열의 최댓값을 구해서 해결할 수 있습니다. 하지만 2차원 쿼리는 귀찮기 때문에 플레인 스위핑을 사용할 것입니다.

$x$좌표를 기준으로 스위핑합시다. 구체적으로, $x_2$를 만나면 $[y_2,y_1+k]$ 구간을 1 증가시키고, $x_1+k$를 지나면 $[y_2,y_1+k]$를 구간을 1 감소시킵니다. 구간에 어떤 값을 더하는 쿼리와 수열의 전체 원소의 최댓값을 구하는 쿼리를 처리해야 하고, 이는 세그먼트 트리로 처리할 수 있습니다.
각 $x$좌표에서의 이벤트를 모두 처리한 다음 세그먼트 트리의 루트 정점의 값을 참조하는 방식으로 구현하면 전체 문제를 $O(N \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
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 21;

int T[SZ<<1], L[SZ<<1];

void Push(int node, int s, int e){
    T[node] += L[node];
    if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
    L[node] = 0;
}

void Update(int l, int r, int v, int node=1, int s=0, int e=SZ-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) / 2;
    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(int l, int r, int node=1, int s=0, int e=SZ-1){
    Push(node, s, e);
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return T[node];
    int m = (s + e) / 2;
    return max(Query(l, r, node<<1, s, m), Query(l, r, node<<1|1, m+1, e));
}

struct Event{
    int t, l, r, v;
    Event() = default;
    Event(int t, int l, int r, int v) : t(t), l(l), r(r), v(v) {}
    bool operator < (const Event &e) const { return t < e.t; }
};

int K, N, R, X1, Y1, X2, Y2;
vector<Event> E;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> X1 >> Y2 >> X2 >> Y1 >> K >> N; X1 += K; Y1 += K; E.reserve(N+N);
    for(int i=0; i<N; i++){
        int r2, c2, r1, c1; cin >> r2 >> c1 >> r1 >> c2;
        r2 += K; c2 += K;
        if(r1 <= r2 && c1 <= c2) E.emplace_back(r1, c1, c2, +1), E.emplace_back(r2+1, c1, c2, -1);
    }
    sort(E.begin(), E.end());
    for(int i=0, j=0; i<E.size(); i=j){
        while(j < E.size() && E[i].t == E[j].t) Update(E[j].l, E[j].r, E[j].v), j++;
        // if(X1 <= E[i].t && E[i].t <= X2) R = max(R, Query(Y1, Y2));
        Push(1, 0, SZ-1); R = max(R, T[1]);
    }
    cout << R;
}