• 먼저 알아둘 테크닉은, i번째 원소의 값이 어떤 구간 [l, r] 안에서 유일하게 존재하는지를 O(1)에 찾는 방법이다.
  • 각 원소 A[i]에 대해서, 같은 값을 갖는 원소중 i보다 앞에 있으면서 가장 큰 인덱스를 갖는 원소를 찾아서 prev라는 배열에 저장해두자. 대충 prev[i] = max(x) where A[x] = A[i] and x < i. 마찬가지로 i보다 뒤에 있으면서 가장 작은 인덱스의 원소도 찾아서 next[i]에 저장해두자. 그러면 A[i] 와 같은 값이 [l,r]에 유일하게 존재하는지는 prev[i]<l && next[i]>r 과 동치가 된다.
  • next와 prev는 O(n)에 전부 계산할 수 있다.
• 자 이제 본론으로 돌아와서, 어떤 구간 [l, r]이 non-boring sequence가 되는지를 분할정복으로 확인해보자.
• [l, r] 안에서 A[i]가 유일하게 존재하는 원소라면, i를 포함하는 구간은 모두 유일한 원소가 있으니, [l, i-1] 과 [i+1, r]만 non-boring sequence가 된다면 [l, r]이 non-boring sequence가 된다.
• 따라서, 주어진 구간 내의 원소들에 대해서 하나씩 유일성 체크를 수행해서, 유일한 원소를 찾으면 그 위치를 기준으로 둘로 분할해서 처리하는 것을 반복하면 된다. 하지만, 한쪽 끝에서 시작해서 유일한 원소가 나올때까지 리니어 스캔을 하면, O(n)이 걸린다. 만약 이렇게 둘로 분할한 결과가 언밸런스해서, 예를 들면 유니크한 원소가 항상 n번째에 있어서 찾기 위해서 n개의 원소를 체크해야하고, 분할한 뒤에 크기 n-1짜리 구간이 생긴다면, 전체 시간복잡도가 O(n^2)이 된다.
• 하지만 여기에서도 Small to Large의 원리를 적용할 수 있다. 직접적으로 원소를 특정 집합에서 다른 집합으로 옮기는 것은 아니지만, 두개의 집합으로 나누는 것은 동일하다. 따라서 한 구간을 분할하는 작업의 시간을 작은 구간의 크기에 바운드시킬수 있다면, 전체 구간을 1짜리 구간들로 모두 분할하는데 걸리는 시간복잡도를 O(nlogn)으로 맞출수 있다. 여기에서는 양 끝에서부터 탐색을 하기 시작해서 유일한 원소가 나올때까지 체크하면, '작은 집합의 크기' * 2 번만의 체크로 분할 위치를 찾을수 있다.

(다이아몬드 이상은 코드 첨부 생략)