BOJ)2336 굉장한 학생

문제:icpc.me/2336

N명이 학생이 세번의 시험을 치뤘을 때 A라는 학생이 B라는 학생보다 세번의 시험의 성적이 모두 좋다면 A가 B보다 '대단하다'고 한다.

어떤 학생 C가 자신보다 대단한 학생이 없을 경우 C는 '굉장하다'라고 한다.

N명의 학생의 3번의 시험에서의 등수가 주어졌을 때 굉장한 학생의 수를 구하는 문제이다.

굉장한 학생을 다시 정의하자면 자기보다 세번의 시험을 전부 다 잘본 학생이 한명도 없는 경우이다.

우리는 굉장한 학생을 구하기 위해 첫번째 시험의 등수 기준으로 정렬을 할 것이다.

그리고 첫번째 시험을 잘 본 순서대로 쿼리를 처리할 것이다.

이러면 먼저 나온 학생이 적어도 그 뒤에 나온 학생들보다 1번째 시험을 잘봤다는 것은 자명한 사실이니 뒤에 나오는 학생들의 2,3번째 시험과 관계없이 뒤에 나오는 학생들이 앞에 나온 학생보다 굉장한 학생일 확률은 0%이다.

따라서 우리는 쿼리를 정렬한 후 순서대로 처리해주면 자기보다 먼저 나온 학생이 자기보다 2,3번째 시험을 동시에 잘본 경우가 없는 경우에 굉장한 학생이다 라고 처리를 해줄 수 있다.

그렇다면 문제를 어떻게 풀어나가야 할까?

우리는 세그먼트 트리의 구간의 최솟값을 이용하여 문제를 풀 예정이다.

우선 전 노드를 INF로 초기화 시켜준 후 

쿼리를 처리 할 때마다 2번째 등수의 위치에 3번째 등수를 업데이트 시켜준다.

그렇다면 우리는 쿼리를 처리 할 때 1~나의 2번째 등수의 구간을 확인한다면 나보다 1,2번째 시험을 잘본 학생들의 구간을 확인하는 것이다.

구간에는 3번째 시험의 등수가 업데이트 되어있을 것이기 때문에 구간의 최솟값이 나의 3번째 시험의 등수보다 작다면 나보다 대단한 학생이 존재하는 것이므로 현재 처리하는 쿼리는 굉장한 학생이 아니게 된다.

이를 이용하여 문제를 풀면 된다.

#include <cstdio>
#include <algorithm>
#define INF 987654321
#define MAX_N 500000
using namespace std;
struct student {
    int x, y, z;
};
bool cmp(student a, student b) {
    return a.x < b.x;
}
student s[MAX_N];
int n, seg[4 * MAX_N], res, t;
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = min(update(pos, val, node * 2, x, mid), update(pos, val, node * 2 + 1, mid + 1, y));
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return INF;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return min(query(lo, hi, node * 2, x, mid), query(lo, hi, node * 2 + 1, mid + 1, y));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t);
        s[t].x = i;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t);
        s[t].y = i;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t);
        s[t].z = i;
    }
    sort(s + 1, s + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
        update(i, INF, 1, 1, n);
    for (int i = 1; i <= n; i++) {
        if (query(1, s[i].y, 1, 1, n)>s[i].z)
            res++;
        update(s[i].y, s[i].z, 1, 1, n);
    }
    printf("%d\n", res);
    return 0;
}