알고리즘 (segtree) 시간복잡도 $O(NlogN)$ 풀이 $g(K)$, 즉 배열 중 $1\sim K$만을 고려하는 경우를 생각해보자. $f(K, y, z)$가 가질 수 있는 최댓값은 구간 $[l, r]$ 중 $K$ 이하의 원소의 개수이다. 이를 각 원소 관점에서 생각해본다면, 가능한 $g(K)$의 최댓값은 모든 $K$ 이하의 자연수 $i$에 대해 $i$의 값을 가지는 위치를 $p(i)$라 할 때 $p(i) \times (N-p(i)+1)$의 합임을 알 수 있다. $a_1, a_2, ..., a_N$에서 $K$ 이하의 원소만을 고른 부분수열을 $b_1, b_2, ..., b_K$라 하면, $f(K, y, z)$의 실젯값은 위에서 구한 이론적인 값에서 $b_i < b_{i+1} < b_{i+2}$ 또는..
