백준[baekjoon] 2336

www.acmicpc.net/problem/2336

2336번: 굉장한 학생

이 문제는 스위핑 + 세그먼트 트리를  이용한 문제이다.

체인점(2472) 문제와 풀이가 유사하다.

 

"굉장한 학생 수"를 구하기위해 "전체 학생수" - "굉장하지 않은 학생수"를 빼면 되고,

 

"굉장하지 않은 학생수"를 구하기 위해

a.x < b.x && a.y < b.y && a.z < b.z      **(x,y,z)는 시험등수, (a,b)는 학생

를 만족하는 b학생은 굉장하지 않은 학생이된다. (a학생이 b학생보다 대단하기 때문)

 

이를 판별하기 위해 첫번째 시험등수(x)를 오름차순으로 정렬하고

세그먼트 트리값은 [0 ... 두번째 시험등수(y)]에 해당하는 학생의 세번째 시험등수(z) 최솟값을 보관하면된다.

 

T라는 학생이 있다고 가정해보자

세그먼트 트리 [0 ... T.y -1] 값이 존재한다면, T.x 등수보다 우수하고(오름차순으로 정렬하였기 때문),

트리의 범위는 T.y 등수보다 우수하며 ( [0 ... T.y -1] < T.y ),

트리의 범위 해당하는 값(세번째 시험등수)이 T.z 보다 작다면 

T학생보다 대단한 학생이 존재하기 때문에 T 학생은 "굉장하지 않은 학생" 임을 알 수 있다.

 

<코드>

#include<bits/stdc++.h>

using namespace std;

const int treeSize = 1<<19;
const int INF = 0x3f3f3f3f;

int tree[treeSize << 1];
int n;

void update(int idx, int val)
{
    idx += treeSize;
    tree[idx] = min(tree[idx], val);
    while(idx > 1){
        idx >>= 1;
        tree[idx] = min(tree[idx << 1], tree[idx << 1|1]);
    }
}

int query(int left, int right)
{
    int ret = INF;
    for(left += treeSize, right += treeSize; left<=right; left>>=1, right >>=1){
        if(left%2 == 1){
            ret = min(ret, tree[left++]);
        }
        if(right%2 == 0){
            ret = min(ret, tree[right--]);
        }
    }
    return ret;
}

struct node
{
    int x, y, z;

    bool operator<(const node& rhs)
    {
        if(x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    } 
}nodeList[treeSize];


int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    memset(tree, 0x3f, sizeof(tree));
    cin >> n;

    int r;
    for(int i=1; i<=n; i++){
        cin >> r;
        nodeList[r].x = i;
    }

    
    for(int i=1; i<=n; i++) {
        cin >> r;
        nodeList[r].y = i;
    }
    for(int i=1; i<=n; i++) {
        cin >> r;
        nodeList[r].z = i;
    }

    sort(nodeList+1, nodeList+n+1);

    int none = 0;
    for(int i=1; i<=n; i++){
        int tmp = query(0,nodeList[i].y-1);
        if(tmp != INF && tmp < nodeList[i].z){
            none++;
        }

        update(nodeList[i].y, nodeList[i].z);
    }

    cout << n-none << '\n';
    return 0;
}