Universal Cup Judging System

Universal Cup

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

小 L 有一個正三角形網格,其中每條網格線都係連接相鄰兩邊對應嘅 $n$ 等分點嘅線段。呢啲網格線將個大正三角形分割成若干個全等嘅細正三角形。

對於圖入面網格線嘅每個交點,我哋用座標 $(x, y)$ 嚟表示。由上至下嘅 $x$ 座標範圍係 $1$ 到 $n + 1$。$x = 1$ 代表最頂端嘅點,而 $x = n + 1$ 代表最底嗰條線。對於第 $i$ 行,由左至右嘅網格點嘅 $y$ 座標範圍係 $1$ 到 $i$。

喺三角形網格入面,有若干個正三角形,佢哋嘅方向可能係正向(朝上)或者反向(朝下)。對於每種方向嘅三角形,我哋用三個數 $x, y, d$ 嚟表示。其中,$(x, y)$ 代表佢平行於網格底邊嘅嗰條邊所對嘅頂點座標,而 $d$ 代表佢嘅邊長(線段嘅長度)。

例如,喺下圖入面,藍色正三角形係一個正向三角形,佢嘅 $(x, y, d) = (4, 2, 3)$。黃色正三角形係一個反向三角形,佢嘅 $(x, y, d) = (6, 3, 2)$。

而家,對於每個單位細正三角形網格(邊長為 $1$ 嘅正三角形,無論方向點樣),上面都寫住一個數字。一開始,網格上面嘅所有數字都係 $0$。小 L 會執行以下操作:

  • 揀一個正三角形,將佢入面所有網格上面嘅數字都加 $w$。
  • 揀一個正三角形,查詢佢入面所有網格上面嘅數字總和。

佢希望你可以計出每次查詢操作嘅答案。由於小 L 唔鍾意大數,你只需要輸出答案對 $2^{32}$ 取模後嘅結果。

輸入格式

輸入嘅第一行包含兩個整數 $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$)。

接住落嚟嘅 $q$ 行,每行代表一次操作。

每行開頭有五個數 $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$ 代表操作類型,其中 $opt = 1$ 係修改操作,而 $opt = 2$ 係查詢操作。$type$ 表示呢次操作入面三角形嘅類型,其中 $type = 0$ 代表正向三角形,而 $type = 1$ 代表反向三角形。$x, y, d$ 用嚟描述呢個三角形。如果 $opt = 1$,仲會有一個額外嘅數 $w$ ($0 \le w < 2^{32}$),表示呢次修改操作入面加上去嘅數值。

保證所有輸入嘅三角形面積都唔為零,而且全部都係完全包含喺大三角形內部嘅合法三角形。

輸出格式

對於每個 $opt = 2$ 嘅查詢,喺新嘅一行輸出一個數,代表該區域內數字總和對 $2^{32}$ 取模後嘅結果。

範例

輸入格式 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

輸出格式 1

20
11
3

輸入格式 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

輸出格式 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.