k594. 解題愛老鼠（多重宇宙 - 白色世界）

內容

自從老鼠在西元 526522 年的 Zerojudge 上解題數登上第一名後，他除了偶爾更新一下自己的題目讓它保持在「最近更新」的最上面之外，沒有什麼其它有趣的事可以做了，於是他想到他可以到其它多重宇宙，在其它宇宙的 Zerojudge 上也登上第一名。

他叫肯肯肯 send 他製造機器的 code 之後，他打造了一臺宇宙穿越器，用了這個機器，他可以穿越到其它宇宙了！

他首先來到的宇宙是「白色世界」，這個世界原本全部東西都是白色的，經過某個人拿著黑色顏料染黑後，文字已經變成黑色了。

這個宇宙的 Zerojudge 同樣有 $10^{18}$ 題，如果把「解題統計」看成一個 2D 平面，那麼它會是一個大小為 $10^{9} \times 10^{9}$ 的平面，在座標為 $(x, y) (1 \leq x, y \leq 10^{9})$ 的題目會有一個值 $a_{x, y}$ ，代表老鼠在此題提交的次數，每題初始時次數都是 $0$ 。

老鼠接下來會有 $q$ 次操作，每次操作可能有兩種形式，第 $1$ 種會給 $x, y, k$ ，代表要在座標為 $(x, y)$ 的題目提交 $k$ 次，也就是使 $a_{x, y}$ 增加 $k$ ；第 $2$ 種會給 $u, d, l, r$ ，代表要詢問座標 $(x, y)$ 在 $u \leq x \leq d, l \leq y \leq r$ 範圍內題目的總提交次數是多少，也就是 $\sum_{x = u}^{d} \sum_{y = l}^{r} a_{x, y}$ 是多少。

由於這個宇宙裡其他人都不寫 blog，老鼠沒辦法複製 code，所以請你幫幫老鼠！如果你讓老鼠登上第一名，老鼠會請你吃粽子並答應讓你的名字出現在他的題目上！

輸入說明

第一行有 $q$ 個正整數，代表操作次數。

接下來 $q$ 行，每行第一個正整數是 $t$ ：

如果 $t = 1$ ，代表要做第 $1$ 種操作，會繼續輸入三個正整數 $x, y, k$ 。

如果 $t = 2$ ，代表要做第 $2$ 種操作，會繼續輸入四個正整數 $u, d, l, r$ 。

$1 \leq q \leq 2 \times 10^{5}$
$1 \leq x, y, k \leq 10^{9}$
$1 \leq u \leq d \leq 10^{9}$
$1 \leq l \leq r \leq 10^{9}$

輸出說明

對於每個 $t = 2$ 的操作，請輸出一個整數代表 $\sum_{x = u}^{d} \sum_{y = l}^{r} a_{x, y}$ 是多少。

範例輸入 #1

2
1 99 88 1000
2 98 100 81 90

範例輸出 #1

範例輸入 #2

10
1 21 27 35
1 2 81 2
2 38 96 49 80
1 57 6 59
2 24 65 22 80
1 76 36 49
2 7 86 31 80
2 2 89 1 37
1 7 34 8
2 44 66 10 81

範例輸出 #2

範例輸入 #3

20
1 857308423 34368234 712916841
1 655705527 363499430 898291977
1 980402899 509116282 730759588
2 375446845 604419051 426300217 497813912
2 166362130 523750832 951299513 968108339
1 779781503 366461409 267664110
1 461205768 688965087 314652008
1 276535756 519197915 469301063
2 317339667 800646190 16070606 894237590
1 841336131 399252083 723960521
1 179220618 178948243 75375289
1 773284094 87727730 326990805
2 15086360 525098195 147454488 854835212
1 541350901 930474951 637543154
2 531312413 955952176 320152154 384880507
2 712391657 731778501 347833425 622584582
2 85345094 590684241 376191404 424774097
2 464879336 836126544 321344020 939489705
2 231270405 824082371 398949852 583374784
1 691033646 428717912 282101408

範例輸出 #3

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 3.0s , <1M
公開測資點#1 (5%): 3.0s , <1M
公開測資點#2 (8%): 3.0s , <10M
公開測資點#3 (8%): 3.0s , <10M
公開測資點#4 (8%): 3.0s , <10M
公開測資點#5 (8%): 3.0s , <10M
公開測資點#6 (8%): 3.0s , <10M
公開測資點#7 (8%): 3.0s , <10M
公開測資點#8 (8%): 3.0s , <10M
公開測資點#9 (8%): 3.0s , <10M
公開測資點#10 (8%): 3.0s , <10M
公開測資點#11 (9%): 3.0s , <10M
公開測資點#12 (9%): 3.0s , <10M

提示：

$10 % ： n, q, x, y, k, d, r \leq 1000$

$90 % ：無特別限制$

標籤:

分治

出處:

[管理者：

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」