만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

간단한 쿼리 문제

시간 제한3초메모리 제한1024 MB

요약

순열과 구간 질의가 주어질 때, 각 질의의 구간 [l, r] 안에서 i ≤ j인 모든 쌍의 |a_i - a_j| 합을 구합니다.

난이도: 보통10점 중 6점
유형: 배열, 세그먼트 트리, 정렬
정답자: 아직 제출이 없습니다

문제

$1$ 부터 $N$ 까지의 순열 $a_1, a_2, \ldots, a_N$ 이 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

$l$ $r$ : $\sum_{l \leq i \leq j \leq r}{|a_i - a_j|}$ 의 값을 출력한다.

입력

첫째 줄에 순열의 길이 $N$ 과 쿼리의 개수 $Q$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 길이가 $N$ 인 순열이 공백으로 구분되어 주어진다. 셋째 줄부터 $Q+2$ 번째 줄까지 각 쿼리의 $l$ , $r$ 이 공백으로 구분되어 한 줄에 하나씩 주어진다.

출력

각 줄에 쿼리의 정답을 출력한다.

제한

$1 \leq a_i \leq N$
$1 \leq l \leq r \leq N$

예제1

예제 1
입력
```
4 2
4 1 3 2
1 3
2 4
```
예상 출력
```
6
4
```

Loading...