== include(page="template/taskheader" task_id="vaporeon") ==
Poveste şi cerinţă...
!problema/vaporeon?cute_vaporeon.png!
Blanche, liderul echipei Mystic, a fost capturată de echipa Lacheta! Ea a fost adusă într-o bază a echipei care conţine $N$ obstacole numerotate de la $1$ la $N$, fiecare obstacol $i$ având rezistenţa $R[i]$. Iniţial, Blanche este plasată în dreptul celui de-al $x$-lea obstacol. Încercând să scape, ea îl eliberează pe Vaporeon care distruge al $x$-lea obstacol şi capătă puterea de atac $A$ egală cu $R[x]$.
Pentru a evada, Vaporeon trebuie să distrugă toate obstacolele rămase. La un moment de timp la care Vaporeon a distrus toate obstacolele din intervalul $[x, y]$, el poate executa exact una din mişcările:
* $Hydro Pump$ pe obstacolul $x-1$, dacă $x-1 ≥ 1$ şi $R[x-1] ≤ A$.
* $Hydro Pump$ pe obstacolul $y+1$, dacă $y+1 ≤ N$ şi $R[y+1] ≤ A$.
* $Work Up$, care creşte puterea de atac $A$ la valoarea minimă dintre $R[x-1]$ şi $R[y+1]$. Dacă doar unul din obstacole există, puterea de atac creşte la valoarea rezistenţei acestuia.
O mişcare $Hydro Pump$ necesită efort $1$, în timp ce o mişcare $Work Up$ necesită efort $K$. Notăm cu $E[x]$ efortul necesar evadării pornind din al $x$-lea obstacol. $E[x]$ este egal cu suma minimă a eforturilor necesare pentru a distruge cele $N$ obstacole, dacă Vaporeon a început din al $x$-lea obstacol.
Echipa Lacheta a anticipat această strategie, aşa că studiază diferite aranjamente ale obstacolelor, cât şi diferite poziţii în care să o plaseze iniţial pe Blanche. Ei vă vor da numărul de obstacole $N$, efortul $K$ necesar unei mişcări şi rezistenţele celor $N$ obstacole. Apoi, ei vă vor cere să efectuaţi următoarele operaţii:
* Să schimbaţi două obstacole adiacente $x$ şi $x+1$.
* Să spuneţi, pentru doi indici $x$ şi $y$, care este suma $E[x] + E[x+1] + … + E[y]$ pentru aranjamentul actual al obstacolelor.
h2. Date de intrare
Fişierul de intrare $vaporeon.in$ ...
Primul rând al fişierului de intrare $vaporeon.in$ va conţine pe $N$ şi $K$.
Următorul rând va conţine valorile lui $R$, separate prin câte un spaţiu.
Vor urma descrierile operaţiilor, una pe câte un rând. Daca $P$ este răspunsul celei mai recente operaţii de al doilea tip (sau $0$ dacă nu au fost încă astfel de operaţii), atunci operaţiile se vor codifica astfel:
* $1 X$ reprezintă interschimbarea lui $X xor P$ şi $(X xor P) + 1$
* $2 X Y$ reprezintă o operaţie de găsire a sumei $E[X xor P] + … + E[Y xor P]$
h2. Date de ieşire
În fişierul de ieşire $vaporeon.out$ ...
Fişierul de ieşire $vaporeon.out$ va conţine răspunsurile pentru toate operaţiile de al doilea tip, câte una pe un rând.
h2. Restricţii
h2. Restricţii şi precizări
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ K ≤ 1.000.000$
* $1 ≤ R[i] ≤ 1.000.000.000$
* Numărul total de operaţii este mai mic sau egal cu $200.000$
* Pentru $20%$ din teste, $N ≤ 1.000$ şi numărul total de apeluri la funcţiile exchange şi query nu depăşeşte $2.000$.
h2. Exemplu
table(example). |_. vaporeon.in |_. vaporeon.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
| 5 3
2 3 1 4 1
2 2 2
2 6 2
1 36
2 36 36
2 12 8
| 7
38
13
41
|
h2. Explicaţie
Operaţiile efectuate sunt:
* Una de al doilea tip pentru a calcula $E[2]$
* Una de al doilea tip pentru a calcula $E[1] + E[2] + E[3] + E[4] + E[5]$
* Una de primul tip asupra lui $2$
* Una de al doilea tip pentru a calcula $E[2]$
* Una de al doilea tip pentru a calcula $E[1] + E[2] + E[3] + E[4] + E[5]$
== include(page="template/taskfooter" task_id="vaporeon") ==
