12738 가장 긴 증가하는 부분 수열3

[EvergreenTree97]

범위 압축 + 세그먼트 트리 문제

• 범위 압축(객체를 하나 만들어서, comparator로 정렬하면)

  1. 오름차순 정렬
  2. 중복 제거하고 1,2,3,4 인덱싱
  3. 인덱스가 값이 됨

• 인덱스 트리 (tree[i] = num[i]를 마지막으로 하는 LIS의 길이)

  1. j가 i보다 앞에 있고 (j < i)
  2. i보다 작은 수(A[j] < A[i]) 인
  3. j중에 가장 긴 LIS 길이를 찾고 , A[i]인 자기 자신의 길이 +1 해주는 식으로 tree 채우기