백준 1615 - 교차개수세기

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

힌트

이 문제를 풀기 위해선 inversion counting에 대한 지식이 있어야 한다.

 

문제에 주어진 형태처럼 교차 그래프가 주어졌을 때의 LIS 문제를 풀어본 경험이 있다면 이것도 비슷하게 접근할 수 있다. 생각해보자!

---

풀이

교차 그래프가 주어지고 몇개의 간선이 교차하는지 알아내야 한다.

 

어느 쪽 노드 집합을 기준으로 정렬을 한 후 반대 쪽 노드 집합들의 나열 형태를 보면서 교차 간선의 개수를 세보자.

 

그러면 inversion counting의 형태를 띄는 것을 관찰할 수 있다.

 

자세한 설명은 동일한 유형의 문제 풀이를 참조하라.

 

그대로 inversion counting의 개수를 출력해주면 된다.

 

전체 코드

#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 n, m;

pii ar[2000 * (2000 - 1) / 2 + 1];
ll fenwick[2001];

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

ll sum(int pos)
{
  ll ret = 0;

  while (pos)
  {
    ret += fenwick[pos];
    pos &= (pos - 1);
  }

  return ret;
}

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

  cin >> n >> m;

  for (int i = 0; i < m; ++i)
    cin >> ar[i].first >> ar[i].second;
  
  sort(ar, ar + m);

  ll res = 0;

  for (int i = m - 1; i >= 0; --i)
  {
    res += sum(ar[i].second - 1);
    add(ar[i].second, 1);
  }

  cout << res;
}

제출 기록