[백준 2336번] [세그먼트 트리 / 스위핑] 굉장한 학생

Approach

상당히 재밌는 문제이다.

문제를 요약하자면, 3개의 시험에 대해서 모두 다 우월한 학생이 있는지를 판단하는 것이 굉장히 중요하다.

 

일단 첫번째 시험을 기준으로 오름차순으로 정렬을 한다.

정렬된 결과에서 앞에 위치하는 학생은 적어도 첫번째 시험을 더 잘 본 것이므로, 해당 학생보다 뒤에 위치하는 학생은 굉장한 학생한 학생을 판단하는 과정에서 고려하지 않아도 된다. 따라서 첫 시험을 기준으로 정렬을 한 뒤, 해당 학생의 앞에 있는 학생 중 2, 3번째 시험을 모두 더 잘 본 학생이 없다면 해당 학생은 굉장한 학생이라고 판단해주면 된다.

 

따라서, 이 문제를 풀기 위해서 실질적으로 해결해야하는 부분은

"해당 학생의 앞에 있는 학생 중 2, 3번째 시험을 모두 더 잘 본 사람이 있는지 여부"이다.

1번째 시험을 고려하지 말고, 2, 3번째 시험만 고려하여 상황을 단순화시켜보자.

그렇게 되면, 2번째 시험이 i등인 학생이 굉장한 학생임을 판단하기 위해서는 2번째 시험이 1등 ~ i - 1등까지의 학생들의 세번째 시험의 최솟값보다 현재 2번째 시험이 i등인 학생의 3번째 시험의 등수보다 더 큰 것이 있는지를 판단해주면 된다. 만약 더 작은 것이 존재하면 현재 학생은 굉장한 학생이 아니고, 그렇지 않으면 굉장한 학생이 된다. 잘 보면, 1 ~ i - 1등까지의 구간의 최솟값을 지속적으로 구하고 있는 상황이 반복되고 있음을 파악할 수 있고 따라서 Min segment tree를 활용하여, 해당 구간의 최솟값을 구하여 굉장한 학생 여부를 판단할 수 있게 된다.

 

첫번째 시험까지 고려하기 위해서는 어떻게 하면 될까?

그렇게 하기 위해서는 모든 노드를 INF로 초기화해주고, 첫번째 시험을 잘 본 순서대로 해당 학생이 굉장한 학생인지를 판단해주고, segment tree를 update해주는 과정을 거치면 된다.(세그먼트 트리에는 3번째 등수에 대한 정보를 저장하게 된다.). 먼저 처리한 것들에 대해서만 INF값을 가지지 않으므로,구간 1 ~ i - 1등까지의 구간에 대한 정보값을 확인하는 것과 해당 학생보다 1, 2번째 시험을 모두 잘 본 학생들의 구간을 확인하는 것은 동치다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};

class ptr{
    public:
    int x, y, z;
};

bool cmp(ptr &v1, ptr &v2){
    return v1.x < v2.x;
}

const int sz = 500010;
ptr arr[sz];
int tree[4 * sz];
const int INF = 2000000000;

int update(int node, int start, int end, int idx, int value){
    if(idx < start || end < idx) return tree[node];
    if(start == end) return tree[node] = value;
    int mid = (start + end) >> 1;
    return tree[node] = min(
        update(node * 2, start, mid, idx, value),
        update(node * 2 + 1, mid + 1, end, idx, value)
    );
}

int query(int node, int start, int end, int left, int right){
    if(right < start || end < left) return INF;
    if(left <= start && end <= right) return tree[node];
    int mid = (start + end) >> 1;
    return min(
        query(node * 2, start, mid, left, right),
        query(node * 2 + 1, mid + 1, end, left, right)
    );
}

int main() {
    fastio;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        arr[t].x = i;
    }

    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        arr[t].y = i;
    }

    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        arr[t].z = i;
    }

    sort(arr + 1, arr + n + 1, cmp);
    fill(&tree[0], &tree[4 * sz], INF);
    int ret = 0;
    for(int i = 1; i <= n; i++){
        if(query(1, 1, n, 1, arr[i].y) > arr[i].z) ret++;
        update(1, 1, n, arr[i].y, arr[i].z);
    }

    cout << ret << "\n";
}