백준14463 소가 길을 건너간 이유 9

작성일 | In

문제 링크

  • http://icpc.me/14463

문제 출처

  • 2017 Feb USACO Gold 3번

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(N \log N)$

풀이

$i$번째 소를 처음 본 시간을 $A_i$, 두번째로 본 시간을 $B_i$라고 합시다.
두 소 $i, j$가 만나기 위해서는

  • $A_i \leq A_j \leq B_i$
  • $A_i \leq B_j \leq B_i$
  • $A_j \leq A_i \leq B_j$
  • $A_j \leq B_i \leq B_j$

중 하나 이상 만족해야 합니다.

이런 $(i, j)$ 쌍을 찾는 것은 $(A_i, B_i)$ 들을 정렬해준 뒤, 스위핑하는 것으로 간단히 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 14463 소가 길을 건너간 이유 9

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

ll tree[1 << 18];
const int sz = 1 << 17;
void update(int x, int v){
    x |= sz; tree[x] += v;
    while(x >>= 1) tree[x] = tree[x << 1] + tree[x << 1 | 1];
}
ll query(int l, int r){
    l |= sz; r |= sz; int ret = 0;
    while(l <= r){
        if(l & 1) ret += tree[l++];
        if(~r & 1) ret += tree[r--];
        l >>= 1; r >>= 1;
    }
    return ret;
}

int n;
p a[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n+n; i++){
        int t; cin >> t;
        if(!a[t].x) a[t].x = i;
        else a[t].y = i;
    }
    sort(a+1, a+n+1);
    ll ans = 0;
    for(int i=1; i<=n; i++){
        ans += query(a[i].x, a[i].y);
        update(a[i].y, 1);
    }
    cout << ans;
}