백준(BOJ) 2336 굉장한 학생 ***

세그먼트 트리를 사용하는 문제이다.

이 문제에서는 "데이터 입력을 어떻게 처리하냐가" 중요한것 같다.

상당히 이해하기도 어려웠고 까다로웠던 문제였다.

굉장한 학생이란 3번의 모든 시험에서 학생 본인보다 대단한 학생이 없는 경우이다. 
입력에서 1,2,3,5가 4명이 굉장한 학생이 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>
#include <set>
#include <utility>
#include <functional>
#define MAX 500005
#define INF 987654321
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;

typedef struct st {
    int first;
    int second;
    int third;
}student;

student arr[MAX];
int n, seg[4 * MAX], ans=0, tmp;

bool cmp(student a, student b) {
    return a.first < b.first;
}

int update(int pos, int val, int cur, int left, int right)
{
    if (right < pos || pos < left)
        return seg[cur];
    if (left == right)
        return seg[cur] = val;
    
    int mid = (left + right)/2;
    return seg[cur] = min(update(pos, val, cur*2, left, mid), update(pos, val, cur*2+1, mid+1, right));
}
int query(int dleft, int dright, int cur, int left, int right)
{
    if (right < dleft || dright < left)
        return INF;
    if (dleft <= left&&right <= dright)
        return seg[cur];
    
    int mid = (left + right)/2;
    return min(query(dleft,dright,cur*2,left,mid), query(dleft,dright,cur*2+1,mid+1,right));
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmp);
        arr[tmp].first = i;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmp);
        arr[tmp].second = i;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &tmp);
        arr[tmp].third = i;
    }

    sort(arr + 1, arr + 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, arr[i].second, 1, 1, n)>arr[i].third)
            ans++;
        update(arr[i].second, arr[i].third, 1, 1, n);
    }
    
    printf("%d\n", ans);
    return 0;
}