Code Submission Evaluation System Login

IOI-leiri 2016

Treap VII


Task | Statistics


CSES - Treap VIICSES - Treap VII

Time limit:5.00 s Memory limit:256 MB

Tehtävänäsi on ylläpitää $n$ luvun taulukkoa. Aluksi taulukko on täynnä nollia. Taulukkoon tehdään seuraavanlaisia kyselyjä: Lukujonon $(a_0, a_1, a_2, \ldots, a_{n-1})$ polynomihajautusarvo on $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots + a_{n-1} x^{n-1}$ modulo $2^{64}$, missä $x = 123456789$.

Syöte

Syötteen ensimmäisellä rivillä on luvut $n$ ja $q$, taulukon koko ja kyselyiden lukumäärä. Seuraavat $q$ riviä sisältävät kyselyt. Jokaisella kyselyrivillä on ensin merkki, joka kertoo kyselyn tyypin: S, R tai A. Rivin loppu riippuu kyselytyypistä: Tuloste

Tulosta jokaista H-kyselyä kohti välin polynomihajautusarvo $2^{64}$ omalle rivilleen.

Rajat
Esimerkki

Syöte:
8 24
R 7 8
R 2 3
A 1 3 66
H 1 5
A 2 4 43
R 1 4
R 5 6
H 3 8
R 4 8
A 1 7 8
H 6 6
R 1 3
A 4 8 91
H 3 7
H 2 3
R 4 8
R 4 8
H 4 4
H 7 8
A 1 6 74
H 1 6
A 6 6 88
A 5 6 13
H 2 4


Tuloste:
1005944205660722526
8148148183
8
1731100457623044023
6296296356
99
19382715972
12342422904188490918
2636793139215058949