Laiko ribojimas: 0.7s

Atminties ribojimas: 256MB

Duomenų failas: nelyginis.in

Rezultatų failas: nelyginis.out

Jei norite pateikti savo sprendimą - prisijunkite.

Nelyginis kiekis

Ir vėl teks pavargti su Linu ir jo hobiu kolekcionuoti unikalius skaičius :)

Šį kartą jis paėmė visus savo surinktus skaičius (kai kurie iš jų kartojasi) ir kaip karoliukus suvėrė ant ilgos virvutės. Akivaizdu, kad ši karoliukų grandinė nėra graži - joje yra pasikartojančių skaičių. Tačiau kai kurie šios grandinės posekiai atrodo tikrai neblogai, t.y. visada galima surasti posekį, kuris turės bent vieną unikalų skaičių (jei grandinę sudaro skaičiai 1,1,2,1,3, tai posekis [4:5] yra gražus, kadangi jame yra net du unikalūs skaičiai: 1 ir 3).

Didėjant grandinei sąlyginai mažėjo gražių posekių, tačiau Linas pastebėjo, kad jam patinka ne tik tie skaičiai, kurie unikalūs, bet ir tie, kurie kažkokiame posekyje kartojasi nelyginį kiekį kartų. Dabar jam įdomu, kiek yra gražių skaičių kažkokiame jo grandinės posekyje. Žinodamas, kad jums puikiai sekasi skaičiuoti skaičių kiekius, jis paprašė jūsų pagalbos.

Linas planuoja jums uždavinėti klausimus pavidalo Q s e, į kuriuos jums reikės atsakyti parašant kiek nelyginį kartų pasikartojančių skaičių yra posekyje prasidedančiame indeksu s ir pasibaigiančiu e (grandinė numeruojama nuo 1, Q yra fiksuotas simbolis). Linas taip pat gali bet kada atlikti operaciją S i n, po kurios jo grandinės skaičius, kurio pozicija i, bus pakeistas į skaičių n.

Pradiniai duomenys

Pirmoje eilutėje bus du skaičiai N,q (1\\leqN\\leq50000, 0\\leqq\\leq10000). N nurodo skaičių esančių grandinėje kiekį, o q - užklausų kiekį.

Antrojoje eilutėje bus pateikti vienu tarpu atskirti skaičiai a_1,a_2,\\ldots,a_N (1\\leqa_i\\leq1000). Šie skaičiai sudarys Lino grandinę.

Likusiose q eilutėse bus pateiktos Lino užklausos, kurių kiekviena bus arba Q s e (1\\leqs\\leqe\\leqN) arba S i n (1\\leqi\\leqN,1\\leqn\\leq1000) pavidalo.

Rezultatai

Į kiekvieną Q tipo užklausą reiks atsakyti nurodant gražių skaičių kiekį nurodytam intervale (atlikus prieš šią užklausą buvusias S tipo užklausas).

Pavyzdžiai

Pradiniai duomenys Rezultatai
5 5
1 2 2 3 4
S 1 2
Q 1 3
Q 3 5
S 5 2
Q 1 5
1
3
1