CSES - Treap V
  • Time limit: 4.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ä:

  • G: hae taulukon tietyssä kohdassa oleva luku
  • R: käännä taulukon yhtenäinen väli ympäri
  • A: lisää taulukon yhtenäisellä välillä kaikkiin lukuihin annettu arvo

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: G, R tai A. Rivin loppu riippuu kyselytyypistä:

  • G: luku 1\leq i\leq n, taulukon kohdan indeksi
  • R: luvut a ja b, välin alku- ja loppukohdat (1\leq a\leq b\leq n)
  • A: luvut a ja b ja d, välin alku- ja loppukohdat, sekä välin jokaiseen alkioon lisättävä luku, (1\leq a\leq b\leq n)

Tuloste

Tulosta jokaista G-kyselyä kohti annetussa kohdassa oleva luku omalle rivilleen.

Rajat

  • 1\leq n\leq 5\cdot 10^5
  • 1\leq q\leq 5\cdot 10^5
  • 1\leq d\leq 10^{12}

Esimerkki

Syöte:

8 24
R 7 8
R 2 3
A 1 3 66
G 6
A 2 4 43
R 1 4
R 5 6
G 2
R 4 8
A 1 7 8
G 4
R 1 3
A 4 8 91
G 2
G 3
R 4 8
R 4 8
G 6
G 2
A 1 6 74
G 5
A 6 6 88
A 5 6 13
G 2

Tuloste:

0
109
8
117
51
99
117
173
191