Universal Cup Judging System

Universal Cup

Límite de tiempo: 4.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Little L har et reguljært trekantrutenett, der hver rutenettlinje er et linjestykke som forbinder de tilsvarende $n$ delingspunktene på tilstøtende sider. Disse rutenettlinjene deler den likesidede trekanten inn i flere kongruente mindre likesidede trekanter.

Hvert skjæringspunkt mellom rutenettlinjene i figuren representerer vi med en koordinat $(x, y)$. $x$-koordinaten ovenfra og ned går fra $1$ til $n + 1$. $x = 1$ representerer det øverste punktet, mens $x = n + 1$ representerer bunnlinjen. For den $i$-te raden går $y$-koordinatene til rutenettpunktene fra venstre mot høyre fra $1$ til $i$.

I trekantrutenettet er det flere likesidede trekanter, som kan være orientert rettvendt (med spissen opp) eller opp-ned (med spissen ned). For hver orientering av trekanten representerer vi den med tre tall $x, y, d$. Her representerer $(x, y)$ koordinatene til hjørnet som ligger rett overfor siden som er parallell med rutenettets bunnlinje, og $d$ representerer sidelengden (lengden på linjestykket).

For eksempel, i figuren nedenfor er den blå likesidede trekanten en rettvendt trekant med $(x, y, d) = (4, 2, 3)$. Den gule likesidede trekanten er en opp-ned-trekant med $(x, y, d) = (6, 3, 2)$.

Nå er det skrevet et tall på hver liten enhetstrekant i rutenettet (en likesidet trekant med sidelengde $1$, uansett orientering). Til å begynne med er alle tallene i rutenettet $0$. Little L vil utføre følgende operasjoner:

  • Velg en likesidet trekant og legg til $w$ på alle tallene i rutenettfeltene inni den.
  • Velg en likesidet trekant og spør etter summen av alle tallene i rutenettfeltene inni den.

Han håper du kan beregne svaret for hver spørreoperasjon. Siden Little L ikke liker store tall, trenger du bare å skrive ut resultatet av svaret modulo $2^{32}$.

Inndata

Den første linjen i inndataene inneholder to heltall $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

De neste $q$ linjene representerer hver en operasjon.

Hver linje starter med fem tall $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$ representerer typen operasjon, der $opt = 1$ er en endringsoperasjon og $opt = 2$ er en spørreoperasjon. $type$ angir typen trekant for denne operasjonen, der $type = 0$ er for en rettvendt trekant og $type = 1$ er for en opp-ned-trekant. $x, y, d$ beskriver denne trekanten. Hvis $opt = 1$, følger det et ekstra tall $w$ ($0 \le w < 2^{32}$) som angir tallet som legges til under denne endringsoperasjonen.

Det er garantert at alle trekantene i inndataene har et areal ulikt null og er gyldige trekanter som er fullstendig inneholdt i den store trekanten.

Utdata

For hver spørring med $opt = 2$ skal du skrive ut et enkelt tall på en ny linje, som representerer summen innenfor området modulo $2^{32}$.

Eksempler

Inndata 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

Utdata 1

20
11
3

Inndata 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

Utdata 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.