| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 93 | 28 | 25 | 37.879% |
Albert는 정수 배열을 이용한 놀이를 즐겨한다. 길이가 $N$인 정수 배열 $B$가 있을 때, $B_i$는 $B$의 $i$번째 원소를 나타낸다. 또한 $i \le j$일 때, $B_{i:j}$ 는 $i$ 번째부터 $j$ 번째까지의 원소를 포함한 길이가 $(j-i+1)$인 부분배열을 나타낸다. 즉 $B = [5, 3, 1, 2, 4]$ 라면 $N = 5$이고 $B_3 = 1,ドル $B_{3:3} = [1],ドル $B_{2:4} = [3, 1, 2]$ 그리고 $B_{3:4} = [1, 2]$ 이다. 또한, 임의의 부분 배열 $B_{i:j}$ 의 원소 중 최댓값을 $X_{i, j}$로 정의하자. 즉, $X_{i,j} = \max_{i \le k \le j} B_k$ 이다.
Albert는 아래 규칙에 따라 모든 1ドル \le i \le j \le N$인 $i,j$에 대하여 부분 배열 $B_{i:j}$의 점수를 매기는데 이를 $S_{i, j}$라 하자.
예를 들어 $B = [5, 3, 1, 2, 4]$ 일 때, $X_{i,j}$의 값과 $S_{i, j}$ 의 값은 아래 표에 정리 되어있다 (1ドル \le i \le j \le N$인 경우만 고려한다).
위 예제에서 몇 가지 경우를 살펴보자.
Albert는 위와 같은 규칙에 따라 모든 부분 배열의 점수를 구한 후 그 총합이 무엇인지 알고 싶어졌다. 즉, $\sum_{1 \le i \le j \le N} S_{i, j}$ 를 구하면 된다. 위 예제의 경우 정답은 12이다.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에 $N$이 주어진다. 다음 줄에 배열 $B$의 정수 $N$개가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
9 5 1 2 3 4 5 5 5 4 3 2 1 5 5 3 1 2 4 5 3 1 5 2 4 4 1 2 2 1 6 1 6 4 5 3 2 6 6 4 2 1 3 5 8 1 7 1 7 1 7 7 1 1 2023
0 0 12 6 0 3 18 21 0
예제 1-2: 모든 부분 배열의 점수가 0 이다.
예제 3: 본문에서 다루었다.
예제 4: $S_{1, 3} = S_{3, 5} = 3$ 이고 이외의 모든 경우 점수가 0이다.
예제 5: 모든 부분 배열의 점수가 0 이다.
예제 6: $S_{2, 4} = 3$ 이고 이외의 모든 경우 점수가 0이다.
예제 7-9: 추가 설명 없음.