[백준 1615번] 교차개수세기 (C++)

문제링크 : https://www.acmicpc.net/problem/1615

1615번: 교차개수세기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

vector<int> arr[2001];
vector<ll> tree;  //세그먼트 트리
ll result = 0;

ll sum(int start, int end, int left, int right, int node)  //start ~ end : 노드, left ~ right : 구간
{
    if(left > end || right < start) return 0;  //겹치지 않으므로 종료
    if (left <= start && end <= right) return tree[node];  //교집합이 start, end
    int mid = (start + end) / 2;
    return sum(start, mid, left, right, node*2) + sum(mid+1, end, left, right, node*2+1);
}

void update(int start, int end, int node, int idx, int diff)
{
    if(idx < start || idx > end) return;  //겹치지 않으므로 종료
    tree[node] += diff; //변한만큼 갱신

    if(start!=end)  //리프노드가 아니라면 자식도 갱신해줌
    {
        int mid = (start+end)/2;
        update(start, mid, node*2, idx, diff);    //왼쪽 탐색
        update(mid+1, end, node*2+1, idx, diff);  //오른쪽 탐색
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    int i, j;

    for(int n=0; n<M; n++)
    {
        cin >> i >> j;
        arr[i].push_back(j);
    }

    int h = (int)ceil(log2(N));
    tree.resize(1<<(h+1));

    for(int i=1; i<=N; i++)
    {
        for(int j=0; j<arr[i].size(); j++)
        {
            result += sum(1, N, arr[i][j] + 1,  N, 1); //겹친 것의 합 -> i보다 작고 [i][j] 보다 큰 기준으로
        }

        for(int j=0; j<arr[i].size(); j++)
        {
            update(1, N, 1, arr[i][j], 1);  //겹친 부분 갱신
        }
    }

    cout << result;

    return 0;
}

겹치는 방법이

i번보다 크고 [i][j]보다 작은 경우

i번보다 작고 [i][j]보다 큰 경우

이렇게 2가지이다.

 

이번 코드에서는 i번 보다 작고 [i][j]보다 큰 경우만을 카운트했다.