Universal Cup Judging System

Universal Cup

Limite de temps : 4.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Pikku L:llä on säännöllinen kolmioruudukko, jossa jokainen ruudukkoviiva on jana, joka yhdistää vierekkäisten sivujen vastaavat $n$ jakopistettä. Nämä ruudukkoviivat jakavat tasasivuisen kolmion useiksi yhteneviksi pienemmiksi tasasivuisiksi kolmioiksi.

Esitämme kuvan ruudukkoviivojen jokaisen leikkauspisteen koordinaatilla $(x, y)$. $x$-koordinaatti ylhäältä alas vaihtelee välillä $1$ – $n + 1$. $x = 1$ tarkoittaa ylintä pistettä, kun taas $x = n + 1$ tarkoittaa alinta viivaa. Rivillä $i$ ruudukkopisteiden $y$-koordinaatit vasemmalta oikealle vaihtelevat välillä $1$ – $i$.

Kolmioruudukossa on useita tasasivuisia kolmioita, jotka voivat olla oikeinpäin (kärki ylöspäin) tai ylösalaisin (kärki alaspäin). Esitämme kummankin suuntaisen kolmion kolmella luvulla $x, y, d$. Tässä $(x, y)$ tarkoittaa sen kärjen koordinaatteja, joka on vastapäätä ruudukon alareunan suuntaista sivua, ja $d$ tarkoittaa sen sivun pituutta (janan pituutta).

Esimerkiksi alla olevassa kuvassa sininen tasasivuinen kolmio on oikeinpäin oleva kolmio, jolle $(x, y, d) = (4, 2, 3)$. Keltainen tasasivuinen kolmio on ylösalaisin oleva kolmio, jolle $(x, y, d) = (6, 3, 2)$.

Nyt jokaiseen pieneen yksikkökolmioruutuun (tasasivuinen kolmio, jonka sivun pituus on $1$ suunnasta riippumatta) on kirjoitettu luku. Aluksi kaikki ruudukon luvut ovat $0$. Pikku L suorittaa seuraavia operaatioita:

  • Valitse tasasivuinen kolmio ja lisää $w$ kaikkiin sen sisällä olevien ruutujen lukuihin.
  • Valitse tasasivuinen kolmio ja kysy kaikkien sen sisällä olevien ruutujen lukujen summaa.

Hän toivoo, että voit laskea vastauksen jokaiseen kyselyoperaatioon. Koska Pikku L ei pidä suurista luvuista, sinun tarvitsee vain tulostaa vastauksen tulos modulo $2^{32}$.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

Seuraavat $q$ riviä kuvaavat kukin yhden operaation.

Jokainen rivi alkaa viidellä luvulla $opt, type, x, y, d$ ($opt \in \{1, 2\}, type \in \{0, 1\}, 1 \le x \le n + 1, 1 \le y \le x, 1 \le d \le n$). $opt$ ilmaisee operaation tyypin, missä $opt = 1$ on muutosoperaatio ja $opt = 2$ on kyselyoperaatio. $type$ ilmaisee kolmion tyypin tässä operaatiossa, missä $type = 0$ tarkoittaa oikeinpäin olevaa kolmiota ja $type = 1$ ylösalaisin olevaa kolmiota. $x, y, d$ kuvaavat tämän kolmion. Jos $opt = 1$, rivillä on lisäksi luku $w$ ($0 \le w < 2^{32}$), joka ilmaisee tässä muutosoperaatiossa lisättävän luvun.

On taattu, että kaikkien syötteen kolmioiden pinta-ala on nollasta poikkeava ja että ne ovat kelvollisia kolmioita, jotka sisältyvät kokonaan suuremman kolmion sisään.

Tuloste

Tulosta jokaiselle kyselylle, jossa $opt = 2$, omalle rivilleen yksi luku, joka ilmaisee alueen sisällä olevien lukujen summan modulo $2^{32}$.

Esimerkit

Syöte 1

5 5
1 0 3 3 2 2
1 1 6 4 2 3
2 0 1 1 5
2 0 3 2 3
2 1 5 3 2

Tuloste 1

20
11
3

Syöte 2

10 10
1 0 1 1 5 2
1 1 3 2 1 6
1 1 6 4 2 1
2 0 10 3 1
2 1 5 2 1
2 1 6 4 2
1 0 7 7 1 7
1 1 9 3 1 3
1 0 9 5 2 4
2 0 6 1 2

Tuloste 2

0
2
12
0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.