[백준] 13372 : Glass Bridge

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

문제 분석

 강을 기준으로 양쪽 각각 N개의 지점이 존재하고 양쪽 지점을 잇는 N개의 다리를 놓을 때 교차하는 지점의 최대 개수를 구하는 문제이다. 이때, 문제상에서 3개 이상의 다리가 동일한 지점을 교차하는 경우를 배제하였으므로 교차 지점의 위치를 고려할 필요는 없고 두 다리의 교차여부만 판별하면 된다. 
 교차 여부 자체는 간단하게 판별가능하다. 그림과 같이 +지점과 -지점이 있을 때, +지점에서 b다리의 값이 더 크면 -지점에서는 a다리의 값이 두 다리는 교차한다.$($그 반대의 경우도 가능하다.$)$ 하지만 모든 다리쌍에서 교차여부를 판별하려 하면, N이 $[2,100000]$으로 모든 다리쌍을 확인하는 경우는 $N^2$으로 $10^{10}$정도로 TLE가 발생하므로 불가능하다. 따라서, 모든 다리 쌍에서 교차여부를 판별하지않고 효과적으로 교차가 가능한 후보군만을 탐색하는 방법이 필요하다.
 두 다리가 교차하려면 2가지 조건을 만족해야 한다. 편의상 기준이 되는 다리를 a 교차의 후보가 되는 다리를 b라 지칭하겠다. 또한, i다리의 - 지역의 인덱스를 $x_i$, + 지역의 인덱스를 $y_i$라 두겠다. 다리가 교차하려면 하단의 조건을 만족해야 한다. $($물론 두 조건의 부등호의 방향이 바뀌는 것도 가능하지만 이는 단순 a, b의 순서 차이이므로 하단 조건만 사용한다.$)$

1. $x_a<x_b$
2. $y_a> y_b$

조건을 줄이는 방법은 간단하다. 일단 모든 다리를 x값에 대해서 정렬하고 모든 다리를 후보군에 넣은 후, 각 기준이 되는 다리를 x를 기준으로 오름차순으로 방문하며 방문 시 해당 다리를 후보군에서 삭제하면 조건 1은 항상 만족하게 된다. 이제 후보군중에서 조건 2를 만족하는 개수를 찾는 과정만 매 방문 시 마다 수행하면 총 교차개수를 계산이 가능하다.
 문제는 매 방문시 다리를 삭제하는 과정과 조건 2를 만족하는 개수를 검색하는 과정을 $O(n)$보다 작게 끔 수행해야 된다는 것이다. 지점이 주기적으로 업데이트되면서 구간별 계산을 수행하는 자료 구조는 펜윅 트리, 세그먼트 트리 등 여러 가지 있지만 필자는 그중 세그먼트 트리를 사용하여 구현하였다.

문제 해결 전략

기본적인 흐름은 아래를 따라간다. 세그먼트트리의 각 값들은 후보 중 y가 해당 값인 다리의 개수들을 저장하게끔 구성하였다. 

1. 다리의 값들을 $($x, y$)$의 pair 형식으로 저장
2. 저장된 값들을 x를 기준으로 정렬
3. 모든 다리의 y값들을 세그먼트 트리에 추가
4. x가 작은 순으로 다리 방문
4-1. 세그먼트 트리에서 현재 다리의 y값 1 감소
4-2. 세그먼트 트리에서 현재 다리의 y값보다 작은 다리의 개수 검색
4-3. 결괏값에 개수 더하기
5. 결과값 반환

코드

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

struct SegmentTree{
public:
    SegmentTree(int size){
        _size=1;
        while(_size<2*size) _size*=2;
        _data.resize(_size,0);
    }
    int CountCrossing(int value){
        return find(0,_size/2-1,1,value);
    }
    void add(int value){
        update(0,_size/2-1,1,value,1);
    }
    void remove(int value){
        update(0,_size/2-1,1,value,0);
    }
private:
    int update(int lv, int rv, int ind, int targetv, int v){
        int mid=(lv+rv)/2;
        if (lv==rv){
            if(lv==targetv) _data[ind]=v;
        }
        else if (targetv<=mid){
            _data[ind]= update(lv,mid,2*ind,targetv,v)+_data[2*ind+1];
        }
        else{
            _data[ind]= _data[2*ind] + update(mid+1,rv,2*ind+1,targetv,v);
        }
        return _data[ind];
    }

    int find(int lv, int rv, int ind, int v){
        int mid=(lv+rv)/2;
        if (lv==rv){
            return _data[ind];
        }
        else if (v<=mid){
            return find(lv,mid,2*ind,v);
        }
        else{
            return _data[2*ind]+find(mid+1,rv,2*ind+1,v);
        }
    }
    int _size;
    vector<int> _data;
};

int main()
{
    int T;
    cin >> T;
    for (size_t t = 0; t < T; t++)
    {
        int N;
        cin >> N;
        vector<pair<int,int>> bridges;
        SegmentTree sgtree(N);
        for (int x = 1; x <= N; x++)
        {
            int y;
            cin >> y;
            bridges.push_back({x,y});
            sgtree.add(y);
        }
        sort(bridges.begin(),bridges.end());
        
        long long result(0);
        for (int i = 0; i < N; i++)
        {
            //delete i node
            sgtree.remove(bridges[i].second);
            //count lower tahn y
            result+=sgtree.CountCrossing(bridges[i].second);
        }
        cout << result << endl;
    }
}