Universal Cup Judging System

Universal Cup

حد الوقت: 4.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Litli L á reglulegt þríhyrningsnet, þar sem hver netlína er strik sem tengir samsvarandi $n$ skiptipunkta á aðliggjandi hliðum. Þessar netlínur skipta jafnhliða þríhyrningnum í nokkra eins minni jafnhliða þríhyrninga.

Fyrir hvern skurðpunkt netlínanna á myndinni táknum við hann með hnitinu $(x, y)$. $x$-hnitið ofan frá og niður spanna frá $1$ til $n + 1$. $x = 1$ táknar efsta punktinn, en $x = n + 1$ táknar neðstu línuna. Fyrir $i$-tu röðina spanna $y$-hnit netpunktanna frá vinstri til hægri frá $1$ til $i$.

Í þríhyrningsnetinu eru nokkrir jafnhliða þríhyrningar, sem geta snúið rétt (með oddinn upp) eða á hvolfi (með oddinn niður). Fyrir hvora stefnu þríhyrningsins táknum við hann með þremur tölum $x, y, d$. Hér táknar $(x, y)$ hnit hornpunktsins sem er á móti hlið hans sem er samsíða neðstu línu netsins, og $d$ táknar hliðarlengd hans (lengd striksins).

Til dæmis, á myndinni hér að neðan er blái jafnhliða þríhyrningurinn réttur þríhyrningur með $(x, y, d) = (4, 2, 3)$. Guli jafnhliða þríhyrningurinn er þríhyrningur á hvolfi með $(x, y, d) = (6, 3, 2)$.

Nú er tala skrifuð á hvern einingar-smáþríhyrning í netinu (jafnhliða þríhyrning með hliðarlengd $1$, óháð stefnu). Í upphafi eru allar tölur á netinu $0$. Litli L mun framkvæma eftirfarandi aðgerðir:

  • Velja jafnhliða þríhyrning og bæta $w$ við allar tölur á reitunum innan hans.
  • Velja jafnhliða þríhyrning og spyrja um summu allra talna á reitunum innan hans.

Hann vonar að þú getir reiknað svarið fyrir hverja fyrirspurnaraðgerð. Þar sem Litla L líkar ekki við stórar tölur þarftu aðeins að prenta niðurstöðu svarsins modulo $2^{32}$.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

Næstu $q$ línur tákna hver um sig eina aðgerð.

Hver lína byrjar á fimm tölum $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$ táknar tegund aðgerðar, þar sem $opt = 1$ er breytingaraðgerð og $opt = 2$ er fyrirspurnaraðgerð. $type$ gefur til kynna tegund þríhyrnings í þessari aðgerð, þar sem $type = 0$ er fyrir réttan þríhyrning og $type = 1$ er fyrir þríhyrning á hvolfi. $x, y, d$ lýsa þessum þríhyrningi. Ef $opt = 1$ er aukatala $w$ ($0 \le w < 2^{32}$) sem gefur til kynna töluna sem bætt er við í þessari breytingaraðgerð.

Tryggt er að allir þríhyrningar í inntaki hafi flatarmál sem er ekki núll og séu gildir þríhyrningar sem eru algjörlega innan stóra þríhyrningsins.

Úttak

Fyrir hverja fyrirspurn með $opt = 2$ skal prenta eina tölu á nýrri línu, sem táknar summuna innan svæðisins modulo $2^{32}$.

Dæmi

Inntak 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

Úttak 1

20
11
3

Inntak 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

Úttak 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.