#451 LIS와 쿼리 2

문제

지문 언어

길이 $N$ 인 수열 $B$ 의 부분수열은 $B$ 에서 원소를 $0$ 개 이상 제거하여 얻을 수 있는 수열이다. 부분수열에서 원소의 순서는 원래 수열에서의 순서와 같아야 한다.

부분수열의 각 원소가 바로 앞 원소보다 크거나 같다면 그 부분수열을 비감소 부분수열이라고 한다. $f(B)$ 를 $B$ 의 비감소 부분수열 중 가장 긴 것의 길이로 정의한다.

길이 $N$ 인 수열 $A=[A_1,A_2,\cdots,A_N]$ 이 주어진다. 에 대하여

A[x:y]=[A_x,A_{x+1},\cdots,A_y]

로 정의한다.

$Q$ 개의 쿼리가 주어진다. 각 쿼리 $(l,r)$ 에 대하여 다음 값을 구하여라.

\sum_{x=l}^{r}\sum_{y=x}^{r} f(A[x:y])

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 $Q$ 개의 줄을 출력한다. $j$ 번째 줄에는 $j$ 번째 쿼리의 답을 출력한다.

#	점수	제한
1	11	각 테스트 케이스에서 $N,Q \leq 200$ . 모든 테스트 케이스에 대한 $N$ 의 합은 $200$ 이하이다. 모든 테스트 케이스에 대한 $Q$ 의 합은 이하이다.

입력

출력

첫 번째 테스트 케이스의 첫 번째 쿼리에는 $6$ 개의 연속 부분 수열이 포함된다. 각 수열에 대한 $f$ 의 값은 $1,1,2,1,2,1$ 이므로 그 합은 $8$ 이다.