TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

95.0% (151/159)

Submission's AC Ratio

49.2% (265/539)

Tags

Description

你,もも,在跟醬油玩堆石子遊戲……

這個遊戲是在一個 $n \times n$ 的棋盤上玩的。

玩法是這樣:

醬油(莊家)每次有兩種操作
1. 在 $(x,y)$ 那一格上面多放 $z$ 顆石子
2. 問你 $(x_1 ,y_1)$ 到 $(x_2 ,y_2)$ 這個矩形區域總共有多少石頭。
全部答對了你就可以欣賞醬油的收藏。

但是因為棋盤太大了,所以你決定寫個程式來幫助你。

Input Format

第一行有 $1$ 個數字 $n$,代表棋盤大小。
接下來有多筆操作,請讀到 EOF 為止。

每筆操作的格式是這樣
第一種操作:1 x y z $(0 \le x,y<n,−32768 \le z \le 32767)$
第二種操作:2 x1 y1 x2 y2 $(0 \le x_1 \le x_2<n, 0 \le y_1 \le y_2<n)$

Output Format

對於每個第二種操作輸出一行答案。

Sample Input 1

4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3

Sample Output 1

3
4

Hints

14% 的測資滿足 $n \le 300$,詢問數 $\le 30000$
100% 的測資滿足 $n \le 1024$,詢問數 $\le 65000$

Problem Source

Step5
2022/05/16 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0~3 20
2 4~7 20
3 8~11 20
4 12~15 20
5 16~19 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 2
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 3
9 1000 65536 262144 3
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 4
13 1000 65536 262144 4
14 1000 65536 262144 4
15 1000 65536 262144 4
16 1000 65536 262144 5
17 1000 65536 262144 5
18 1000 65536 262144 5
19 1000 65536 262144 5