시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 1024 MB | 103 | 64 | 41 | 59.420% |
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.
5 5 4 3 5 1 2 2 3 1 5 4 4 1 4 2 4
0 7 0 4 2
5 2 4 3 1 5 2 2 3 1 5
1 6
6 3 2 6 1 4 3 5 1 5 3 4 1 2
5 0 0
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)$.