알고리즘 (segtree) 시간복잡도 O(NlogN) 풀이 g(K), 즉 배열 중 1∼K만을 고려하는 경우를 생각해보자. f(K,y,z)가 가질 수 있는 최댓값은 구간 [l,r] 중 K 이하의 원소의 개수이다. 이를 각 원소 관점에서 생각해본다면, 가능한 g(K)의 최댓값은 모든 K 이하의 자연수 i에 대해 i의 값을 가지는 위치를 p(i)라 할 때 p(i)×(N−p(i)+1)의 합임을 알 수 있다. a1,a2,...,aN에서 K 이하의 원소만을 고른 부분수열을 b1,b2,...,bK라 하면, f(K,y,z)의 실젯값은 위에서 구한 이론적인 값에서 bi<bi+1<bi+2 또는..
