f992. 線上蛋糕學習 - 高中生程式解題系統

內容

/*草莓蛋糕中可以使用麵糊，並在表面放上草莓；在千層蛋糕之間也可填充草莓，並任意組成；有些則是準備將草莓與糖霜結合。可以使用新鮮或冷凍的草莓；有些則可能以草莓味明膠為原料，當和麵糊混合時，可以給蛋糕粉紅色的顏色；一些草莓蛋糕裡面裝飾草莓，也可當作無麩質飲食小菜。
一些說法是冷凍後並以部分凍結的狀態食用，里考塔有時作為麵糊中的成分或者表面裝飾使用。草莓蛋糕有時以糕點裝飾作為準備基礎，如白色蛋糕組合附加成分添加到麵糊或者蛋糕表面上；有時會在情人節準備並作為菜餚。*/

小貝想要在小克生日時送蛋糕給她，他想要自己製作一個草莓蛋糕，於是他參考了食譜。食譜上說需要麵粉、雞蛋、奶油、砂糖、草莓、蠟燭和打火機，小貝沒有草莓、蠟燭和打火機，所以他去賣場買了蠟燭和打火機，但是草莓剛好缺貨了，於是他去了一趟草莓園。

這裡的草莓很奇特，為一直排 $[1, n]$ ，並且每次都只有區間 $[l, r]$ 的草莓會長大，而且都是以 $k$ 維的方式生長，並且寬度會從左到右依序遞增，也就是從 $l \sim r$ 的草莓每次生長大小分別會增加 $1^{k}, 2^{k}, 3^{k}, . . ., (i - l + 1)^{k}, . . ., (r - l + 1)^{k}$ 。

現在給你每個位置草莓的初始大小，有兩種操作：

使 $[l, r]$ 的草莓生長。
計算 $[l, r]$ 的草莓大小總和。

輸入說明

第一行為 $n, k, q$ ，代表直排長度、草莓生長維度和操作次數。

第二行有 $t_{1} \sim t_{n}$ ，代表草莓初始大小。

接下來 $q$ 行，每行會有 $c, l, r$ ，若 $c = 1$ ，執行操作 $1$ ；若 $c = 2$ ，執行操作 $2$ 。

$1 \leq n, q \leq 10^{5}$
$0 \leq k \leq 3$
$1 \leq t_{i} \leq 10^{9}$
$1 \leq l \leq r \leq n$

輸出說明

對於每個操作 $2$ ，輸出計算結果。

因為答案可能會很大，請 $m o d (10^{6} + 3)$ 再輸出。

範例輸入 #1

8 0 7
15 25 14 13 5 4 23 13
1 5 7
2 2 8
2 2 4
2 2 3
2 2 8
1 2 5
2 1 2

範例輸出 #1

範例輸入 #2

5 1 6
17 22 17 12 26
1 2 5
1 1 5
2 2 4
2 2 2
2 3 4
1 4 5

範例輸出 #2

66
25
41

範例輸入 #3

5 2 10
10 12 18 24 13
2 3 3
2 3 5
2 1 4
1 2 3
2 3 4
1 2 3
2 3 5
2 2 5
1 1 2
2 3 5

範例輸出 #3

範例輸入 #4

8 3 9
11 29 3 26 2 24 11 3
2 4 8
2 1 4
1 6 6
2 1 6
2 2 6
2 2 6
2 3 8
2 4 5
2 4 8

範例輸出 #4

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (2%): 1.0s , <1M
公開測資點#1 (2%): 1.0s , <1M
公開測資點#2 (2%): 1.0s , <1M
公開測資點#3 (2%): 1.0s , <1M
公開測資點#4 (2%): 1.0s , <1M
公開測資點#5 (2%): 1.0s , <1M
公開測資點#6 (2%): 1.0s , <1M
公開測資點#7 (2%): 1.0s , <1M
公開測資點#8 (2%): 1.0s , <1M
公開測資點#9 (2%): 1.0s , <1M
公開測資點#10 (8%): 1.0s , <10M
公開測資點#11 (8%): 1.0s , <10M
公開測資點#12 (8%): 1.0s , <10M
公開測資點#13 (8%): 1.0s , <10M
公開測資點#14 (8%): 1.0s , <10M
公開測資點#15 (8%): 1.0s , <10M
公開測資點#16 (8%): 1.0s , <10M
公開測資點#17 (8%): 1.0s , <10M
公開測資點#18 (8%): 1.0s , <10M
公開測資點#19 (8%): 1.0s , <10M

提示：

$10^{6} + 3$ 為質數。

這一題 $k = 0$ 時相當於這題，只是這題只要加 1 就好； $k = 1$ 時相當於這題。

如果不會用 BIT 解的可以先解上面兩題，如果你要用線段樹解這題，那麼你真的很強。

-------------------------------------------------

$10 % ： q \leq 10^{3}$

$10 % ： n \leq 10^{3}$

$80 % ：無特別限制$

標籤:

BIT 差分

出處:

Caido [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

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