[BOJ] 굉장한 학생

[BOJ] 굉장한 학생

Problem URL : 굉장한 학생

#include<iostream>
#include<algorithm>
#include<vector>
#define MAX 1e9

using namespace std;
struct student {
    int a, b, c;
    bool operator < (student S) {
        return a < S.a;
    }
};
int tree[2000001];
int update(int node, int start, int end, int index, int value) {
    if (index < start || index > end) return tree[node];
    if (start == end) return tree[node] = value;
    else {
        return tree[node] = min(update(node * 2, start, (start + end) / 2, index, value), update(node * 2 + 1, (start + end) / 2 + 1, end, index, value));
    }
}
int getMin(int node, int start, int end, int left, int right) {
    if (start > right || end < left) return MAX;
    else if (start >= left && end <= right) return tree[node];
    else return min(getMin(node * 2, start, (start + end) / 2, left, right), getMin(node * 2 + 1, (start + end) / 2 + 1, end, left, right));
}
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; 
    cin >> n;
    for (int i = 1; i <= 4 * n; i++) tree[i] = MAX;
    vector<student> v(n + 1);
    for (int i = 1; i <= n; i++) {
        int idx; 
        cin >> idx;
        v[idx].a = i;
    }
    for (int i = 1; i <= n; i++) {
        int idx;
        cin >> idx;
        v[idx].b = i;
    }
    for (int i = 1; i <= n; i++) {
        int idx;
        cin >> idx;
        v[idx].c = i;
    }
    sort(v.begin() + 1, v.end());

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        //[1]
        if (getMin(1, 1, n, 1, v[i].b - 1) > v[i].c) ans++;
        //[2]
        update(1, 1, n, v[i].b, v[i].c);
    }
    cout << ans;
}

Comments

[1] i번째 학생보다 두번째 성적이 높은 학생들 중 (트리의 인덱스가 1 ~ v[i].b - 1),
세번째 성적(트리의 값)이 높은 학생이 없으면 i번째 학생은 굉장한 학생이다.
[2] 세그먼트 트리의 인덱스를 두번째 시험 성적(b)로, 세그먼트 트리의 값을 세번째 시험 성적(c)으로 한다.
첫번째 성적의 경우, 자신보다 낮은 성적의 학생의 경우에는 아직 update가 되지 않았기 때문에 (세그먼트 트리에 존재하지 않기 때문에) [1]의 if문 조건식을 거짓으로 만들 수 있지가 않다. 즉, for문이 첫번째 성적이 높은 순서대로 순회하기 때문에 첫번째 성적이 낮은 학생이 높은 학생에게 세그먼트 트리내에서 영향을 끼칠 수 없다.