12899 데이터 구조

www.acmicpc.net/problem/12899

12899번: 데이터 구조

1.접근

N이 2,000,000이므로 NlogN을 생각하게된다. 세그먼트 트리를 이용할텐데 X의 크기도 2000000까지인 것을 보아 리프노드를 200만개로 만들고 1번 유형 쿼리로 숫자와 인덱스가 같은 트리를 만들어야겠다.

2.풀이

우선 트리를 만드는대 어느 숫자가 들어올지 모르기 때문에 리프노드 200만개 모두 만들어야 한다.

그 후 인덱스와 들어오는 숫자가 같은 트리이므로 들어오는 인덱스+size(리프노드전까지의 크기)의 노드에 1을 더해주고 연결된 노드들을 루트노드까지 갱신해준다.

 

2번 유형 쿼리를 해결하려면 X번째 작은수는 리프노드의 왼쪽부터 X번째 수를 찾는다는 걸 이해하고 분할탐색 해야한다.

예를들어 지금 트리에는 5가지 숫자가 들어있다고 하자.

루트노드에는 5 왼쪽 오른쪽 자식노드에 각각2,3이라고 할 때 X가 4인 수를 찾는다고 하면

2보다는 4가 크므로 오른쪽의 3에 원하는 수가 있을 것이다. 따라서 4에서 왼쪽 자식노드의 값 2를 

오른쪽 노드로 가서 3에서 찾는 것이다. 만약 왼쪽 자식 노드가 4이상이였다면 왼쪽을 들어갈 것이다.

그렇게 node가 리프노드 구간일 때 까지 찾고 node값을 출력해주고 -1씩 갱신해주면 된다.

 

3.코드

4.배운점

• x번째로 작은 수 인지 찾는 방법을 오래 고민했는데 200만 밖에 안되므로 그냥 리프노드를 200만개 만들어 버리는 고 왼쪽부터 x번째 수를 찾는 방법을 생각하는데 오래걸렸다. 인덱스와 값이 같은 트리를 만들고 들어 올때마다 1을 더하는 트리에 익숙해지자