[AtCoder] AtCoder Beginner Contest 338 E - Chords C++ 풀이

[문제 링크]
https://atcoder.jp/contests/abc338

[설명]

최대와 최소를 저장하는 세그먼트 트리를 이용하여 문제를 풀었다. A와 B가 들어왔을 때, A에는 B의 값을 넣고 B에는 A의 값을 넣을 것이다. 이때 [A + 1, B - 1] 구간의 최대와 최소를 각각 Max, Min이라 하자. 만약 Max가 B보다 크거나 Min이 A보다 작다면 A와 B를 연결하는 선분은 다른 선분과 교차한다. 왜냐하면 Max가 B보다 크다면 A와 B 사이의 어떤 점과 B를 넘어서는 점을 잇는 선분이 있다는 것이기 때문이다. 마찬가지로 Min이 A보다 작다면 A와 B 사이의 어떤 점과 A를 넘어서지 않는 점을 잇는 선분이 있다는 것이다. 따라서 위와 같은 세그먼트 트리를 구성하여 문제를 해결할 수 있다.

굳이 세그먼트 트리를 만들 필요없이 스택을 이용하여 문제를 쉽게 해결할 수 있다. 또한, 이것이 훨씬 깔끔한 풀이라 생각된다.

[코드]

#include<iostream>
#define pii pair<int, int>
#define Min first
#define Max second
#define INF 1000000
using namespace std;

pii tree[1600004];

pii init(int start, int end, int ind) {
    if (start == end) return tree[ind] = { INF,-INF };
    int mid = (start + end) / 2;
    pii le = init(start, mid, ind * 2), ri = init(mid + 1, end, ind * 2 + 1);
    return tree[ind] = { min(le.Min, ri.Min),max(le.Max, ri.Max) };
}

pii update(int start, int end, int ind, int i, int v) {
    if (i < start || end < i) return tree[ind];
    if (i <= start && end <= i) return tree[ind] = { v,v };
    int mid = (start + end) / 2;
    pii le = update(start, mid, ind * 2, i, v), ri = update(mid + 1, end, ind * 2 + 1, i, v);
    return tree[ind] = { min(le.Min, ri.Min),max(le.Max, ri.Max) };
}

pii res(int start, int end, int ind, int le, int ri) {
    if (ri < start || end < le) return { INF,-INF };
    if (le <= start && end <= ri) return tree[ind];
    int mid = (start + end) / 2;
    pii l = res(start, mid, ind * 2, le, ri), r = res(mid + 1, end, ind * 2 + 1, le, ri);
    return { min(l.Min, r.Min),max(l.Max, r.Max) };
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, i, a, b, tf = 0; cin >> n;
    init(1, 2 * n, 1);
    for (i = 0; i < n; i++) {
        cin >> a >> b;
        if (a > b) swap(a, b);
        pii k = res(1, 2 * n, 1, a + 1, b - 1);
        if (k.Min < a || b < k.Max) tf = 1;
        update(1, 2 * n, 1, a, b);
        update(1, 2 * n, 1, b, a);
    }
    cout << (tf ? "Yes" : "No");
}