사파리나 동물원에서 볼 수 있는 원형 우리를 Boma라고 하는군요. 외국어로 된 문제를 풀다보니 새로운 영단어나 일본어 단어를 종종 알게 되는 경우가 있습니다. 이번에 푼 문제는 Bomas입니다.

\(N\)개의 원형 우리가 있습니다. 여기에 \(Q\)개의 원형 우리 중 하나를 설치할 계획입니다. 이미 설치된 우리 또는 설치할 예정인 우리는 서로 겹치거나 만나지 않습니다. 대신 어느 하나가 다른 하나에 완전히 들어가 있을 수는 있습니다. 원형 우리의 경계를 따라 구역을 나눌 수 있는데, 동물을 어떤 구역에 넣을 때는 인접한 모든 구역이 비어 있어야 합니다. 각각의 설치 예정인 우리에 대해, 동물을 넣을 수 있는 구역 수의 최대값을 구하면 됩니다.

일단 모델링을 좀 단순하게 해봐야겠습니다. 원형 우리는 서로 겹치거나 접하지는 않지만 단지 완전히 포함하는 관계라고 할 때, 이것을 트리로 모델링할 수 있다는 사실을 캐치할 수 있어야 합니다. 바깥에서 둘러싸는 우리는 부모 정점, 안에 들어간 우리를 자식 정점으로 하여 간선을 이어주면 트리가 됩니다.

이렇게 되면 문제에서 요구하는 최대값을 어떻게 구해야 할지도 분명해지는데, 바로 최대독립집합의 크기입니다.

간선으로 연결된 인접 정점 중 하나씩만 고를 수 있을 때, 그렇게 고른 정점 집합을 독립집합이라 합니다. 일반 그래프에서 최대독립집합은 NP문제지만 트리에서만큼은 DP로 다항시간 내에 구할 수 있습니다. 연습문제를 풀어봅시다.

// dp[u][0]: 정점 u를 선택하지 않았을 때의 독립집합 크기. 자식 정점의 두 값에 대해 큰 것을 취하면 됩니다.
// dp[u][1]: 정점 u를 선택했을 때 독립집합 크기. 자식 정점은 고를 수 없으므로 dp[v][0]을 더해줍니다.
void dfs(int u) {
    for (const int& v : graph[u]) {
        dfs(v);
        else {
            dp[u][0] += std::max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
    dp[u][1]++;
}

\(Q\)개의 쿼리로 주어지는 우리 또한 트리의 정점으로 들어가므로 따로 처리해줄 필요 없이 dfs를 조금 변형시켜주면 한꺼번에 처리해줄 수 있습니다. 결국 문제는 어떻게 트리를 만들 것인가가 됩니다.

만약 \(N\)이 충분히 작다면, \(N^2\)개의 포함 관계를 모두 검사하고 위상정렬을 하는 식으로 트리를 만들 수 있습니다. 하지만 이건 이 문제에서는 적용할 수가 없으므로, 다른 방법을 찾아야 합니다.

만약 이 문제에 다음과 같은 서브태스크가 주어진다면 어떻게 할 수 있을까요?

입력으로 주어지는 모든 Y 값은 같다.

마침 좋은 연습 문제가 있습니다. 이 연습 문제를 먼저 해결해봅시다. 서로 겹치는 원이 없다면, 직선 하나를 그어서 얻은 스냅샷은 유효한 괄호문자열이 됩니다. parse tree를 만들 수 있다는 거죠.

이제 논의를 확장해서, 원들이 한 직선 위에 있지 않은 경우까지 생각해 봅시다. 이 경우에도, 임의로 직선 하나를 그어 얻은 스냅샷은 유효한 괄호문자열이 됩니다. 그렇다면 다음 방식으로 트리를 완성할 수 있습니다.

  • Y축에 평행한 모든 직선들에 대한 괄호문자열을 얻습니다.

  • 문자열을 파싱하여 트리를 만듭니다.

모든 직선들을 굳이 검사할 필요는 없습니다. 괄호문자열이 바뀌는 시점들만 검사해주면 되는데, 그 시점은 각각 원 중심 \(x_i\)와 반지름 \(r_i\)에 대해 \(x_i - r_i\) 및 \(x_i + r_i\)가 됩니다.

여기까지만 해서는 아직 시간복잡도가 \(O(N^2)\)입니다.

이제 남은 과제는 괄호문자열에서 삽입, 삭제를 빠르게 해주는 건데, 그 전에 문제를 몇 개 더 풀고 올 필요가 있습니다.

위 문제들에서는 직선을 ordered set에 넣어 관리하면서 시간복잡도를 줄이는 것이 메인 아이디어입니다. 선분 교차 판정에 쓰이는 샤머스-호이 알고리즘은 선분의 삽입, 삭제가 일어나는 모든 스냅샷에 대해 순서가 뒤바뀌는 순간 검사가 종료됩니다. 만일 모든 스냅샷에 대해 순서가 유지된다면 선분을 다 검사할 때까지 알고리즘이 돌아갑니다.

여기서 ordered set에 넣는 게 직선이 아닌 곡선이라 해도, 곡선이 엇갈리지만 않는다면 그 순서를 유지한 채로 집합을 관리할 수 있게 됩니다! 원형 우리를 왼쪽 괄호와 오른쪽 괄호로 분리하여 ordered set에 넣을 생각을 할 수 있는가가 이 문제를 풀 열쇠가 됩니다.

반원에 대해 어느 것이 왼쪽에 있는가를 검사하는 것이 좀 까다로울 수도 있지만, 이 문제에서는 그냥 다른 원의 중심이 반원의 어느 쪽에 있는지만 찾아주면 소수점 계산 없이도 가능합니다.

typedef long long ll;
const int LEN = 1e5 + 1;

struct Pos {
    int x, y;
    bool operator<(const Pos& r) const { return x == r.x ? y > r.y : x < r.x; }
};

ll dist(const Pos& p1, const Pos& p2) { return (ll)(p1.x - p2.x) * (p1.x - p2.x) + (ll)(p1.y - p2.y) * (p1.y - p2.y); }

struct Arc {
    Pos c;
    int r, i;
    bool u;
    bool is_above(const Pos& p) const {
        if (u) { // 위쪽 반원
            if (p.y <= c.y) return 0; // y 좌표가 더 작으면 아래에 있습니다.
            return dist(c, p) > (ll)r * r; // 중심과의 거리가 반지름보다 길면 위에 있습니다.
        }
        if (p.y >= c.y) return 1;
        return dist(c, p) < (ll)r * r;
    }
};

class SplayTree {
    struct Node {
        Node* l;
        Node* r;
        Node* p;
        Arc val;
        Node(int i, bool u) : l(0), r(0), p(0) { val = { circles[i].c, circles[i].r, i, u }; }
        ~Node() { if (l) delete l; if (r) delete r; }
    } *root;
    void rotate(Node* x);
    void splay(Node* x);
public:
    SplayTree() : root(0) {}
    ~SplayTree() { if (root) delete root; }
    void insert(int i) {
        if (!root) {
			// root =  new Node...
            return;
        }
        Node* p = root;
        Node** pp;
        while (1) {
            if (p->val.i == i) return;
            if (p->val.is_above(circles[i].c)) { // 넣으려는 원이 더 위에 있으면
                if (!p->r) { // 오른쪽을 탐색
                    pp = &p->r;
                    break;
                }
                p = p->r;
            }
            else {
                if (!p->l) {
                    pp = &p->l;
                    break;
                }
                p = p->l;
            }
        }
		// pp = new Node...
    }
} sp;