[백준 1615] 교차개수세기

문제

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

 

알고리즘

세그먼트 트리

 

풀이

간선들이 주어질 때, 교차점의 개수를 묻고 있습니다. 교차 조건은 두 개의 에지를 (A1, B1), (A2, B2)라 한다면 A1<A2, B1> B2 또는 A1> A2, B1 <B2이라고 정의하고 있습니다. 이 형태는 1에 해당하는 점을 인덱스라고 고려하고 2에 해당하는 점을 값이라고 할 때, inversion의 정의와 일치하게 됩니다.

 

두 개의 간선을 이중 포문으로 일일이 비교한다면 문제를 해결할 수 있습니다. 하지만 문제에서 제시하는 $edge$개수는 최대 $N^2$ 이므로 $O(N^4)$의 시간복잡도를 갖게 됩니다. 이는 시간초과에 해당합니다.

 

쿼리를 조금 바꿔봅시다. A에 해당하는 점을 index라 하고 B에 해당하는 점을 그 값이라고 정의하겠습니다. 인덱스 순서대로 쿼리를 진행해 나가며, 지금까지 확인한 값들이 현재 값보다 몇개가 큰지를 구하는 것은 두 개의 간선 관계를 비교하는 것과 동등한 쿼리입니다. 이중 포문 전략을 사용할 때는 이 쿼리를 $O(M)$에 해결했지만 세그먼트 트리를 활용하면 $O(logM)$에 해결 가능합니다. 

 

즉 펜윅트리에 지금까지 방문한 값들을 업데이트하며, 보고 있는 값보다 몇 개가 큰지 개수를 카운트하면 됩니다. i <j and A [i]>A [j]에 해당하기 때문입니다(j가 현재 보고 있는 인덱스, i는 이전에 본 인덱스들). 시간 복잡도는 $O(MlogM)$입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef pair<int, int> pii;

long long ans;
int N, M,a,b;
vector<pii> edge;

int fenwick[2001];

void update(int idx, int val) {
    while (idx <= N) {
        fenwick[idx] += val;
        idx += idx & -idx;
    }
}

int query(int idx) {
    int ret = 0;
    while (idx) {
        ret += fenwick[idx];
        idx -= idx & -idx;
    }
    return ret;
}

int main() {
    FAST;
    cin >> N >> M;
    while(M--) {
        cin >> a >> b;
        edge.emplace_back(a, b);
    }
    sort(edge.begin(), edge.end());

    for (auto [A, B] : edge) {
        ans += query(N) - query(B);
        update(B,1);
    }
    cout << ans;
    return 0;
}