ŠIOM — Inversijos 2

Laiko ribojimas: 1s

Atminties ribojimas: 128MB

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Inversijos 2

Jums duotas sąrašas iš $n$ teigiamų sveikųjų skaičių. Pažymėkime $i$ -tąjį sąrašo elementą $a_i$ .

Jums reikia suskaičiuoti kiek yra porų $l,r$ , tokių kad $1\\leql<r\\leqn$ ir seka $a_1,a_2,...a_{l-1},a_l,a_r,a_{r+1},...a_{n-1},a_n$ turi nedaugiau nei $k$ inversijų.

Inversija - tai nesurikiuota elementų pora. Formaliai - inversija yra pora skaičių $i,j$ , tokių kad $i<j$ ir $a_i>a_j$

Pradiniai duomenys

Pirmoje eilutėje yra duoti du skaičiai $n$ ir $k$ ( $2\\leqn\\leq10^5,0\\leqk\\leq10^{18}$ ) - elementų skaičius ir maksimalus galimas inversijų skaičius. Antroje eilutėje yra $n$ skaičių $a_i$ ( $1\\leqa_i\\leq10^9)$ .

Rezultatai

Išveskite vieną skaičių - tinkamų porų $(l,r)$ skaičių.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
3 1 1 3 2	3
5 2 1 3 2 1 7	6

Šeštadieninė informatikos olimpiadininkų mokykla

Inversijos 2

Pradiniai duomenys

Rezultatai

Pavyzdžiai