Universal Cup Judging System

Universal Cup

Time Limit: 4.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Little L har ett regelbundet triangelrutnät, där varje rutnätslinje är ett linjesegment som förbinder motsvarande $n$ delningspunkter på intilliggande sidor. Dessa rutnätslinjer delar in den liksidiga triangeln i flera kongruenta mindre liksidiga trianglar.

För varje skärningspunkt mellan rutnätslinjerna i figuren representerar vi den med en koordinat $(x, y)$. $x$-koordinaten uppifrån och ned går från $1$ till $n + 1$. $x = 1$ representerar den översta punkten, medan $x = n + 1$ representerar den nedersta linjen. För den $i$-te raden går rutnätspunkternas $y$-koordinater från vänster till höger från $1$ till $i$.

I triangelrutnätet finns det flera liksidiga trianglar, som kan vara rättvända (med spetsen uppåt) eller inverterade (med spetsen nedåt). För varje orientering av triangeln representerar vi den med tre tal $x, y, d$. Här representerar $(x, y)$ koordinaterna för det hörn som står mittemot sidan som är parallell med rutnätets baslinje, och $d$ representerar dess sidlängd (längden på segmentet).

Till exempel, i figuren nedan är den blå liksidiga triangeln en rättvänd triangel med $(x, y, d) = (4, 2, 3)$. Den gula liksidiga triangeln är en inverterad triangel med $(x, y, d) = (6, 3, 2)$.

Nu står det ett tal skrivet i varje liten enhetstriangel i rutnätet (en liksidig triangel med sidlängden $1$, oavsett orientering). Från början är alla tal i rutnätet $0$. Little L kommer att utföra följande operationer:

  • Välj en liksidig triangel och addera $w$ till alla tal i rutnätsfälten inuti den.
  • Välj en liksidig triangel och fråga efter summan av alla tal i rutnätsfälten inuti den.

Han hoppas att du kan beräkna svaret för varje frågeoperation. Eftersom Little L inte tycker om stora tal behöver du bara skriva ut resultatet av svaret modulo $2^{32}$.

Indata

Den första raden i indatan innehåller två heltal $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

De följande $q$ raderna representerar var och en en operation.

Varje rad börjar med fem tal $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$ representerar typen av operation, där $opt = 1$ är en ändringsoperation och $opt = 2$ är en frågeoperation. $type$ anger typen av triangel för denna operation, där $type = 0$ står för en rättvänd triangel och $type = 1$ står för en inverterad triangel. $x, y, d$ beskriver denna triangel. Om $opt = 1$ finns det ytterligare ett tal $w$ ($0 \le w < 2^{32}$) som anger det tal som adderas under denna ändringsoperation.

Det garanteras att alla trianglar i indatan har en area skild från noll och är giltiga trianglar som är helt inneslutna i den större triangeln.

Utdata

För varje fråga med $opt = 2$, skriv ut ett enda tal på en ny rad, som representerar summan inom området modulo $2^{32}$.

Exempel

Indata 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

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