[백준] [C++] 5419번 북서풍 (seg tree, sweeping)

1. 문제

https://www.acmicpc.net/problem/5419

5419번: 북서풍

 

 

2. 풀이

- Y 는 감소해야하고 X 는 증가해야한다.

- 이 때 생각할 수 있는 가장 간단한 방법은

- 한 축을 기준으로 정렬을 하고 한개씩 앞에서부터 다른 한축과 비교를 통해 가능한 쌍의 개수를 새나가는것이다.

- 이경우 O(N^2) 의 시간복잡도로 75000 * 75000 = 5,625,000,000 

- 최악의 경우 TLE 가 뜰것이다.

 

그러므로 O(NlogN) 로 문제를 해결해야한다.

- 일단 x축을 기준으로 오름차순으로 정렬, y축은 내림차순으로 정렬해보자.

- 그러면 대충 위와 같은 그림과 같이 나올 것이다.

- 그럼 이제 한 x 에서 쌍을 이룰 수 있는 범위를 그려보자.

- 위 그림과 같이 Y 가 자신보다 작고 자신보다 앞에 있는것들과 쌍을 이룰 수 있다.

- 즉, 구간안에서 Y의 값이 해당 y값보다 작은 것들을 계산하는 구간 트리를 구현하면 문제가 해결된다는 것.

 

- 일단 이 구간트리를 구현하기 앞서

- 1e9 의 입력이 들어오는 y축의 좌표를 압축해야한다 (구간 트리의 끝노드의 범위를 줄여 메모리 절약)

- 압축은 y축을 map에 담아 정렬하여 작은것부터 0 1 2, ... n순서대로 좌표를 할당해주면된다. (아래 코드는 반대 방향)

        for (auto it = dic.end(); it != dic.begin();)
        {   
            it--;
            it->second = maxN++;  // 가장 큰값이 0번
        }
        for (auto &p : point)
        {
            p.second = dic[p.second];
        }

- 이제 크기순으로 재할당된 번호 0, 1, 2, 3 ... 을 끝 노드로 가지는 빈 세그먼트 트리를 만들고,

- 이 세그먼트 트리에 x가 감소하는 방향으로 탐색하면서 

- i ~ n까지의 구간에서 y값이 지금 탐색하고 있는 y보다 더 작은 개수를 먼저 쿼리하고, 

- i 번째에서 y번호를 세그먼트 트리에 추가하여 추가된 노드들의 개수를 가지도록 구간 트리를 update 하면

  (y를 크기순으로 정렬하고 0에서부터 번호를 부여했으므로 이때 까지 추가된 노드들 중에서 y값보다 더 작은 값의 개수를 구할 수 있다.)

- 문제는 해결된다.

 

 

3. 코드

- 구현은 풀이와 반대 방향으로 작성하였다.

// y 는 감소 해야하고 x는  증가해야한다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <map>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

vector<pii> point; // x, y
int n;
int maxN = 0;

struct RQ
{
    vector<int> seg;
    RQ(int n)
    {
        seg.clear();
        seg.resize(n * 4 + 4, 0);
    }
    int query(int lo, int hi, int idx, int qlo, int qhi)
    {
        if (hi < qlo || qhi < lo)
        {
            return 0;
        }
        if (qlo <= lo && hi <= qhi)
        {
            return seg[idx];
        }

        int mid = (lo + hi) / 2;
        int left = query(lo, mid, idx * 2, qlo, qhi);
        int right = query(mid + 1, hi, idx * 2 + 1, qlo, qhi);
        return left + right;
    }
    int update(int lo, int hi, int idx, int pos)
    {
        if (hi < pos || lo > pos)
        {
            return seg[idx];
        }
        if (lo == hi)
        {
            return seg[idx] = seg[idx] + 1;
        }
        int mid = (lo + hi) / 2;
        int left = update(lo, mid, idx * 2, pos);
        int right = update(mid + 1, hi, idx * 2 + 1, pos);
        return seg[idx] = left + right;
    }
};

ll solve()
{
    ll answer = 0;
    RQ rq(maxN);

    for (int i = 0; i < point.size(); i++)
    {
        answer += (ll)rq.query(0, maxN, 1, 0, point[i].second);
        rq.update(0, maxN, 1, point[i].second);
    }
    return answer;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        maxN = 0;
        cin >> n;
        point.clear();
        point.resize(n);
        map<int, int> dic;
        for (int i = 0; i < n; i++)
        { // x , y
            cin >> point[i].first >> point[i].second;
            dic[point[i].second]++;
        }
        sort(point.begin(), point.end(), [](pii &a, pii &b)
             {
                 if (a.first == b.first)
                 {
                     return a.second > b.second;
                 }
                 else
                 {
                     return a.first < b.first;
                 }
             });
        for (auto it = dic.end(); it != dic.begin();)
        {
            it--;
            it->second = maxN++;
        }
        for (auto &p : point)
        {
            p.second = dic[p.second];
        }
        cout << solve() << "\n";
    }
}

 

 

 

4. 비슷한 문제

 

744 Div3 e2, 17131 

- 어떠한 한 값을 기준으로 그 값보다 작은 것의 개수 와 큰 것의 개수를 구하는것

- 이때 17131번은 스택같은 자료구조를 이용하여 y값이 같은것은 한번에 업데이트 시켜야한다.