CSES - Treap V
  • Time limit: 4.00 s
  • Memory limit: 256 MB

Tehtävänäsi on ylläpitää nn 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 nn ja qq, taulukon koko ja kyselyiden lukumäärä. Seuraavat qq 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 1in1\leq i\leq n, taulukon kohdan indeksi
  • R: luvut aa ja bb, välin alku- ja loppukohdat (1abn1\leq a\leq b\leq n)
  • A: luvut aa ja bb ja dd, välin alku- ja loppukohdat, sekä välin jokaiseen alkioon lisättävä luku, (1abn1\leq a\leq b\leq n)

Tuloste

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

Rajat

  • 1n51051\leq n\leq 5\cdot 10^5
  • 1q51051\leq q\leq 5\cdot 10^5
  • 1d10121\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