5419번: 북서풍 - 스위핑, 세그먼트 트리(머지 소트 트리), 이분 탐색

 

1.

모든 점에 대해서 완전 탐색을 돌릴 수는 없으므로, 다른 방법을 생각해 보자. 우선 y좌표가 작은 순으로, y좌표가 같다면 x좌표가 큰 순으로 점들을 정렬한다. 

 

ex) (5, 3), (5, 2), (3, 1), (3, 2), (1, 7), (1, 5) -> (1, 7), (1, 5), (3, 2), (3, 1), (5, 3), (5, 2)

 

여기서 문제 조건을 생각해 보자. 한 점에서 다른 점으로 북서풍을 타고 이동할 수 있으려면, 그 다른 점이 한 점보다 y좌표는 큰 대신 x좌표는 작아야 한다. 위의 예시에서 (5, 3)이 이동할 수 있는 점은 (1, 7), (1, 5) 둘 뿐이다.

 

그런데 현재 y좌표가 작은 순대로, y좌표가 같다면 x좌표가 큰 순으로 정렬되어 있으므로, 우리는 (3, 1)의 왼편에 있는 좌표 중 (3, 1)보다 x좌표가 큰 점의 개수만 고르면 된다. 즉 우리는 이 문제를 정렬된 순서대로 점들을 하나씩 살펴보는 스위핑 기법을 적용하면서, 현재 점보다 x좌표가 큰 점의 개수를 고르는 문제로 바꿀 수 있다.

 

2.

그렇다면 현재 점보다 x좌표가 큰 점의 개수는 어떻게 알 수 있는가? 현재 점의 index를 i라 할 때, 첫 번째 점부터 i번째 점까지의 구간에서 x좌표가 더 큰 점의 개수를 반복적으로 구해야 한다. 즉 구간 질의 문제이므로 세그먼트 트리를 이용해 이 문제를 해결할 수 있다.

이때, '첫 번째 점부터 i번째 점까지의 구간에서 x좌표가 더 큰 점의 개수'는, 첫 번째 점부터 i번째 점이 오름차순으로 정렬되어 있다면 이분 탐색으로 \(O(nlogn)\)으로 빠르게 구할 수 있다. 즉, 세그먼트 트리를 머지 소트 트리로 이용해, x좌표가 정렬된 벡터 배열로 활용하고 이분 탐색으로 x좌표가 더 큰 점의 개수를 빠르게 구할 수 있다.

 

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

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

#define F first
#define S second
const int SIZE = 75000;
vector<pii> point;
int pn = 1;
vector<int> segTree[SIZE * 4];

auto cmp = [](pii p1, pii p2) //y좌표가 작은 것 먼저, y좌표가 같다면 x좌표가 큰 것 먼저 정렬
{
    auto [y1, x1] = p1;
    auto [y2, x2] = p2;
    
    if(y1 != y2) return y1 < y2;
    else return x1 > x2;
};

void build(int idx)
{
    if(idx >= pn)
    {
        segTree[idx].push_back(point[idx-pn].S);
        return;
    }
    
    build(idx*2);
    build(idx*2+1);
    
    int l = 0, r = 0;
    while(l < segTree[idx*2].size() && r < segTree[idx*2+1].size())
    {
        int pl = segTree[idx*2][l], pr = segTree[idx*2+1][r];
        if(pl < pr) segTree[idx].push_back(pl), l++;
        else segTree[idx].push_back(pr), r++;
    }
    while(l < segTree[idx*2].size())
    {
        int pl = segTree[idx*2][l];
        segTree[idx].push_back(pl), l++;
    }
    while(r < segTree[idx*2+1].size())
    {
        int pr = segTree[idx*2+1][r];
        segTree[idx].push_back(pr), r++;
    }
}

int cntLand(int l, int r, int m)
{
    ll ret = 0;
    
    l += pn, r += pn;
    while(l <= r) //이분 탐색
    {
        if(l%2==1) 
        {
            ret += segTree[l].size() - (lower_bound(segTree[l].begin(), 
                    segTree[l].end(), m) - segTree[l].begin());
            l++;
        }
        if(r%2==0) 
        {
            ret += segTree[r].size() - (lower_bound(segTree[r].begin(), 
                    segTree[r].end(), m) - segTree[r].begin());
            r--;
        }
        l /= 2, r /= 2;
    }
    return ret;
}

void solve()
{
    pn = 1;
    point.clear();
    for(int i=0; i<SIZE*4; i++) segTree[i].clear();
    
    int n; cin >> n;
    for(int i=0; i<n; i++)
    {
        int y, x; cin >> y >> x;
        point.push_back({y, x});
    }
    sort(point.begin(), point.end(), cmp); //점 정렬
    
    while(pn < n) pn *= 2;
    build(1); //머지 소트 트리 만들기
    
    ll ans = 0;
    for(int i=0; i<n; i++)
        ans += cntLand(0, i-1, point[i].S); //해당 점에서 갈 수 있는 점 개수 세기
    cout << ans << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int T; cin >> T;
	while(T--) solve();
}

 

3번 과정에서 '첫 번째 점부터 i번째 점까지의 구간에서 x좌표가 더 큰 점의 개수'를 구하는 과정은, 점들을 좌표 압축해서 구간 합을 구하는 것으로도 가능하다.