[Python] 백준 2336 - 굉장한 학생

https://www.acmicpc.net/problem/2336

 

풀이

일단 문제 설명은 살짝 복잡하지만 잘 읽고 보면, "Inverse Count 문제 유형의 응용이구나"를 알게 된다.

 

시험이 세 개 있는데, 위에서부터 A, B, C 시험이라고 하자.

 

A에서 1등한 사람부터 살펴볼 것이다.

약간의 관찰을 해 보면, A에서 1등한 사람부터 살펴볼 때, 그 사람의 (B에서의 등수, C에서의 등수)가 있을 것인데 이거를 하나씩 추가해나가다 보면, 이미 있던 사람의 B, C 등수보다 둘 다 등수가 크게 되는 경우가 존재하면 그 사람은 굉장한 학생이 아니다.

이걸 효과적으로 관리해주기 위해서 세그먼트 트리를 이용한다.

 

A에서 1등한 사람부터 살펴보는 데, 세그먼트 트리의 B에서의 등수 인덱스에 C에서의 등수 값을 넣어준다.

여기서, 세그먼트 트리는 최솟값을 찾아주는 세그먼트 트리이다.

 

만약 0번 인덱스부터 그 사람의 B에서의 등수 인덱스까지 '존재하는' 값들(C에서의 등수) 중 최솟값이 지금 사람의 C에서의 등수보다 크다면 지금 추가하려는 사람은 굉장한 학생이다.

 

이 방법으로 A, B, C에서의 등수를 동시에 관리해줄 수 있다.

 

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
Bidx = [0]*N
Cidx = [0]*N
for i in range(N):
    A[i] -= 1
    B[i] -= 1
    C[i] -= 1
for i in range(N):
    Bidx[B[i]] = i
    Cidx[C[i]] = i

size = 1
while size < N:
    size <<= 1
tree = [1000000]*(2*size)
#size -= 1

def update(idx, diff):
    idx += size
    while idx:
        tree[idx] = min(tree[idx], diff)
        idx //= 2

def search(l, r):
    l += size
    r += size
    ans = 1000000
    while l <= r:
        if l % 2 == 1:
            ans = min(ans, tree[l])
            l += 1
        l //= 2
        if r % 2 == 0:
            ans = min(ans, tree[r])
            r -= 1
        r //= 2
    return ans
cnt = 0
for i in range(N):
    now = A[i]
    update(Bidx[now], Cidx[now])
    if search(0, Bidx[now]-1) > Cidx[now]:
        cnt += 1
print(cnt)