Inverzije

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

요약

순열과 M개의 구간이 주어질 때, 각 구간 안에서 i<j이고 P_i>P_j인 쌍의 개수를 구한다.

난이도: 보통10점 중 7점
유형: 누적 합, 정렬, 분할 정복
정답자: 아직 제출이 없습니다

문제

Neka je zadana permutacija $P$ duljine $N$ . Permutacija duljine $N$ je niz čiji su elementi različiti prirodni brojevi od $1$ do $N$ . Broj inverzija neke permutacije je broj parova $(i, j)$ takvih da je $1 ≤ i < j ≤ N$ i $P\_i > P\_j$ .

Isto tako, broj inverzija permutacija $P$ na intervalu od a do b je broj parova $(i, j)$ takvih da je $a ≤ i < j ≤ b$ i $P\_i > P\_j$ .

Tvoj zadatak je da za zadanu permutaciju $P$ i $M$ zadanih intervala odrediš broj inverzija na svakom od njih.

입력

U prvom su retku prirodni brojevi $N$ ( $1 ≤ N ≤ 100\\,000$ ) i $M$ ( $1 ≤ M ≤ 100\\,000$ ), brojevi iz teksta zadatka.

U drugom retku je $N$ različitih prirodnih brojeva $P\_i$ ( $1 ≤ P\_i ≤ N$ ).

U sljedećih $M$ redaka su prirodni brojevi $a\_i$ i $b\_i$ ( $1 ≤ a\_i ≤ b\_i ≤ N$ ), granice intervala čiji broj inverzija tražimo.

출력

Za svaki od $M$ intervala ispiši broj inverzija permutacije $P$ unutar njega.

힌트

Opis prvog probnog primjera: Na intervalu od $2$ . do $3$ . elementa nema inverzija jer je $3<5$ . Interval od $1$ . do $5$ . elementa je zapravo cijeli niz. Inverzije su u tom slučaju parovi elemenata s indeksima $(1, 2)$ , $(1, 4)$ , $(1, 5)$ , $(2, 4)$ , $(2, 5)$ , $(3, 4)$ i $(3, 5)$ .

예제3

예제 1

입력

예상 출력

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