#451 LIS와 쿼리 2

Statement

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

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

길이 $N$ 인 수열 $A=[A_1,A_2,\cdots,A_N]$ 이 주어진다. $1 \leq x \leq y \leq 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$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $l_1\ r_1$ $l_2\ r_2$ $\vdots$ $l_Q\ r_Q$

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

#	점수	제한
1	11	각 테스트 케이스에서 $N,Q \leq 200$ . 모든 테스트 케이스에 대한 $N$ 의 합은 $200$ 이하이다. 모든 테스트 케이스에 대한 $Q$ 의 합은 $200$ 이하이다.
2	24	$A_i \leq 2$ ( $1 \leq i \leq N$ ).
3	25	각 테스트 케이스에서 $N,Q \leq 200\,000$ . 모든 테스트 케이스에 대한 $N$ 의 합은 $200\,000$ 이하이다. 모든 테스트 케이스에 대한 $Q$ 의 합은 $200\,000$ 이하이다.
4	40	추가적인 제약이 없다.

입력

출력

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

두 번째 테스트 케이스의 수열은 비감소한다. 첫 번째 쿼리에서 각 연속 부분 수열의 길이를 모두 더하면 $20$ 이다.