[ICPC] 백준 5419 - 북서풍

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

힌트

문제에서는 남동쪽 방향으로 가라고 하지만 조건을 생각하면 북서쪽 방향으로 간다고 해도 동일한 결과를 얻을 수 있다.

 

어떤 섬에 도착했을 때 그 섬과 짝이 될 수 있는 섬의 개수를 효율적으로 셀 수 있겠는가?

 

이에 대해 감이 잘 오지 않으면 먼저 세그먼트 트리에 대해 공부한다.

풀이

구간 트리로 다음 구간을 관리한다.

 

해당 구간에 해당하는 좌표를 가진 섬이 출현한 횟수의 합

 

이렇게 되면 낮은 좌표를 가진 섬부터 구간에 반영하면서 해당 섬과 연결될 수 있는 섬의 개수를 세주면 가능하다.

 

그러면 좌표를 정렬해야 할 텐데 어떻게 정렬해줘야 할까?

 

문제를 보면 무조건 동남쪽 방향으로 섬을 이어야 할 것 같지만 달리 생각하면 북서쪽으로 이어도 결과에 차이는 없다.

 

4개의 섬 중 일부를 이은 그림. 북서쪽 방향으로 잇나 남동쪽 방향으로 잇나 4개의 섬을 모두 이을 수 있다.

 

따라서 X 좌표의 오름차순이 첫 번째 기준, Y 좌표의 내림차순이 두 번째 기준으로 삼아 정렬한 후 정렬된 컨테이너의 끝부터 처음까지 순회한다.

 

구간 트리를 쓸 것이므로 좌표압축을 하는 것을 잊지 말자.

 

그러면 X 좌표가 작아지는 방향으로 좌표를 탐색할 것인데 각 좌표마다 연결될 수 있는 섬의 개수를 구간 합 쿼리로 더한 뒤 현재 섬이 나타났다는 정보를 구간에 반영해주면 총 $O(N \log N)$의 시간 복잡도로 답을 구할 수 있다.

 

구현에는 펜윅트리를 써서 시간을 단축했다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

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

int t;
int n;
ll fenwick[75001];
vector<int> press;
vector<pii> crd;

void add(int pos, int val)
{
  while (pos <= 75000)
  {
    fenwick[pos] += val;
    pos += (pos & -pos);
  }
}

ll sum(int pos)
{
  ll ret = 0;
  while (pos)
  {
    ret += fenwick[pos];
    pos &= (pos - 1);
  }
  return ret;
}

void solve()
{
  cin >> t;

  while (t--)
  {
    crd.clear();
    press.clear();
    memset(fenwick, 0, sizeof fenwick);

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
      int x, y;
      cin >> x >> y;
      crd.push_back({x, y});
      press.push_back(y);
    }

    sort(crd.begin(), crd.end(), [](pii &l, pii &r) {
      if (l.first != r.first) return l.first < r.first;
      return l.second > r.second;
    });

    sort(press.begin(), press.end());
    press.erase(unique(press.begin(), press.end()), press.end());

    ll ans = 0;

    for (int i = 0; i < crd.size(); ++i)
    {
      crd[i].second = lower_bound(press.begin(), press.end(), crd[i].second) - press.begin() + 1;
      ans += sum(75000) - sum(crd[i].second - 1);
      add(crd[i].second, 1);
    }

    cout << ans << '\n';
  }
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}

제출 기록