Segment Tree 응용 (2) - Inversion counting , LIS, 3-elements.

세그먼트 트리를 이용하여 구할 수 있는 다양한 값들을 소개하려고 한다. 그 중 이번 포스팅은 사람들에게는 Inversion counting이나 LIS등으로 더 친숙한 2-elements 문제나, 특정 문제에서 사용되어진 3-elements 문제에 대해서 말해보려고 한다.

2-elements는 하나의 객체가 2가지 요소 (두개의 값, 하나의 값과 입력순서 등) 를 가지고 있으며 그 두가지 요소가 모두 작은 객체의 갯수 (LIS) , 둘 다 작은 객체의 존재 여부, 둘의 우선 순서가 뒤바뀐 쌍의 수(inversion counting)등을 구하는 문제이다.

3-elements는 하나의 객체가 3가지 요소를 가지고 있으며 세가지 요소가 모두 작은 객체의 존재여부 등을 다루는 문제이다 (굉장한 학생)

2-Elements 는 보통 1가지 요소를 사전 정렬로써 처리하고 1가지 요소를 업데이트 위치로써 처리한다.
1. 1가지 요소에 대해서 작은 순서로 정렬한다. 그 순서대로 아래의 과정들을 진행한다. 
2. 나머지 한가지 요소에 대해서 그 요소가 해당하는 위치를 구하고 이를 이용해 그 객체에 대한 원하는 값을 구한다.
2-1. 객체의 해당 위치가 i라고 할 때 1~i-1 중 가장 큰 값을 구하고 1을 더하면 LIS를 구할 수 있다
2-2. 객체의 해당 위치가 i라고 할 때 i+1~n 의 갯수를 구하면 inversion 카운팅을 할 수 있다.
3. 2에서 뒤에 얻고자 하는 값을 고려하여, 해당 위치에 필요한 값을 업데이트 한다. 

3-Elements 문제는 보통 3가지 요소가 모두 작은 객체의 존재성을 묻는 BOJ의 굉장한 학생 과 같은 문제가 나오게 된다. 이 역시 1가지 요소를 사전 정렬로써 해결한다.
1. 1가지 요소에 대해서 작은 순서로 정렬한다. 그 순서대로 아래의 과정들을 진행한다. 
2. 두번째 요소에 대해서 그 요소가 해당하는 위치를 구하고 이를 이용해 그 객체에 대한 원하는 값을 구한다.
2-1. 객체의 해당 위치가 i라고 할 때 1~i-1 중 가장 큰 값을 구하고 이 값이 현재 확인하는 객체의 세번째 값보다 작은지를 판단하여 현재 객체보다 3가지 요소가 모두 작은 객체의 존재성을 판단할 수 있다.
3. i의 위치에 3번째 값을 업데이트 한다.

이런식으로 내가 세그트리에서 어떠한 값들을 얻을 수 있고, 어떤 순서로 업데이트를 하느냐에 따라서 정말 다양하게 활용할 수 있는 결과를 얻어낼 수 있다.