JOISC14 Scarecrows

문제

https://oj.uz/problem/view/JOI14_scarecrows

문제 보기 - 허수아비 (JOI14_scarecrows) :: oj.uz

평면 상에 N개의 점들이 주어져 있을때 다음 조건을 만족하는 점들의 순서쌍의 수를 세는 문제이다.

1. 이 두 점을 잇는 직선은 기울기가 양수이다.

2. 이 두 점을 꼭짓점으로 하는 직사각형의 내부에는 어떠한 점도 없다.

 

풀이

점들을 하나씩 오른쪽으로 훑고 지나가는 라인 스위핑을 하며, 그 점을 오른쪽 위 꼭짓점으로 하는 직사각형들의 수를 세 보자. 이 점을 "기준 점"이라 부르자.

 

 

이때, 왼쪽 아래 점이 될수 있는 점들은 기준 점에서부터 왼쪽으로 차례차례 봤을 때, y좌표가 기준 점보다 높은 점들을 제외하고, y좌표가 오름차순이여야 한다.

 

이때 이러한 점들의 수를 그냥 세주면 $O(N^2)$ 으로 비효율 적이다. 따라서 효율적인 자료구조를 사용해 시간을 $NlogN$ 으로 감소시켜야 한다.

 

점들을 노드에 저장하고 있는 세그먼트 트리를 만들자.

물론 점들 사이의 상대적인 위치만 중요하기 때문에 처음에 좌표압축을 해주고 시작한다.

이때 저장하고 있는 노드들은 y좌표를 기준으로 한다. ( y좌표가 1~10까지 존재한다면 1~5 사이의 점들을 노드에 저장하는 방식이다. )

 

노드에 저장해야 하는 값들은 현재까지 본 x좌표 구간 (1~xnow) 에서, 그 노드에게 할당된 y좌표 구간 (yl, yh) 구간의 점들 중 위 그림의 검정색 점처럼 앞에서 보면 내림차순 모양의 노드들만 x좌표 순으로 저장해 준다.

여기서 인지해야 할 점은 세그트리의 아래 단계에서 이미 제거당한 점들은 그 위의(부모의) 노드들에서 다시 부활할 일이 없다는 점이다.

 

이렇게 세그트리를 정의하면, 두가지 연산을 $logN$ 만에 처리해야 한다.

 

1. update

어떠한 내림차순 수열에 새로운 점 하나가 추가되었다.

이 새로운 점은 가장 최신에 본 점이기 때문에, x좌표가 가장 크다.

따라서 이미 저장된 배열에 이 점보다 y좌표가 작은 점들이 있다면 제거해 준 후 이 점을 추가하는 연산을 반복해 주면 된다.

히스토그램 문제나, Bad Hair Day 문제에서 스택을 이용해 라인 스위핑으로 푸는 것과 매우 비슷한 느낌으로, 각 점은 최대 $logN$ 개의 구간에 포함되며, 최대 한번 들어갔다, 나오기 때문에 ammortized time complexity 는 $NlogN$이다.

시간 복잡도 : $O(NlogN)$

 

2. query

새로운 점이 들어오면 그 점을 오른쪽 꼭짓점으로 하는 값들을 알고 싶다.

따라서 세그트리에 1~y 에 대한 쿼리를 때리면 된다.

위 그림에서 빨간색 점들이 위 노드, 파란색 점들이 아래 노드이면, 직선으로 연결된 점들의 수를 세주고 싶다.

즉, 아래 노드의 x좌표 전까지 빨간색 점들을 타고 가다가 파란색으로 옮겨타면 된다.

이때 이용할 수 있는 것들은 점들이 x좌표 오름차순이자 y좌표 내림차순으로 정렬되어 있다는 것이다.

이는 바로 이분탐색이 가능함을 의미한다.

점들의 수와 마지막 점의 x좌표를 전역으로 저장하거나 함수의 인자로 넘겨주면 쉽게 구현할 수 있다.

어디서 아래 노드로 넘어가야 할지를 이진탐색으로 해주면 $logN$ 개의 노드들에 대해 이진탐색 $logN$ -> $log^2N$ 에 처리 가능하다.

시간 복잡도 : $O(log^2N)$

 

구현상 주의해야 할 부분들은 답이 long long 일 수 있으며, query 연산에서 배열이 비어있을 경우도 생각해야 한다는 점이다.

 

개인적으로 문제는 간단하고 풀이는 아름다운 매우 좋은 문제다.

 

시간 복잡도 : $O(NlogN+Nlog^2N) = O(Nlog^2N)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

struct Point
{
    int x, y;
    Point() {}
    Point(int x, int y) : x(x), y(y) {}
    bool operator < (const Point& p)
    {
        return x<p.x;
    }
};

int n;
ll ans;
Point arr[MAXN+10];
vector<int> xpos, ypos;
int xcoord[MAXN+10];

vector<vector<Point>> tree;

void update(int node, int tl, int tr, int x, int y)
{
    if(tl==tr) { tree[node]=vector<Point>(1, Point(x, y)); return; }
    int mid=tl+tr>>1;
    if(y<=mid) update(node*2, tl, mid, x, y);
    else update(node*2+1, mid+1, tr, x, y);

    while(!tree[node].empty() && tree[node].back().y<y) tree[node].pop_back();
    tree[node].push_back({x, y});
}

int last=-1, ret=0;
void query(int node, int tl, int tr, int l, int r)
{
    if(r<tl || tr<l) return;
    if(l<=tl && tr<=r)
    {
        if(tree[node].empty()) return;
        ret+=tree[node].end()-lower_bound(tree[node].begin(), tree[node].end(), Point(last, 0));
        last=max(last, tree[node].back().x);
        return;
    }
    int mid=tl+tr>>1;
    query(node*2+1, mid+1, tr, l, r);
    query(node*2, tl, mid, l, r);
}

int main()
{
    int i, j;
    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        scanf("%d%d", &arr[i].x, &arr[i].y);
        xpos.push_back(arr[i].x);
        ypos.push_back(arr[i].y);
    }
    sort(xpos.begin(), xpos.end());
    sort(ypos.begin(), ypos.end());

    for(i=0; i<n; i++)
    {
        arr[i].x=lower_bound(xpos.begin(), xpos.end(), arr[i].x)-xpos.begin()+1;
        arr[i].y=lower_bound(ypos.begin(), ypos.end(), arr[i].y)-ypos.begin()+1;
    }

    sort(arr, arr+n, [&](const Point& p, const Point& q)
    {
        return p.x<q.x;
    });

    tree.resize(n*4+10);

    for(i=0; i<n; i++)
    {
        last=-1, ret=0;
        query(1, 1, n, 1, arr[i].y);
        ans+=ret;
        update(1, 1, n, arr[i].x, arr[i].y);
    }

    printf("%lld", ans);
}