回『基礎題庫』
f992. 線上蛋糕學習
標籤 : BIT 差分
通過比率 : 3人/3人 ( 100% ) [非即時]
評分方式：
Tolerant

最近更新 : 2021-10-25 21:04

內容

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

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

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

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

  1. 使 $\color{black}{[\ l\ ,\ r\ ]}\ $ 的草莓生長。
  2. 計算 $\color{black}{[\ l\ ,\ r\ ]}\ $ 的草莓大小總和。

輸入說明

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

第二行有 $\color{black}{t_1\sim t_n}\ $，代表草莓初始大小。

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

  • $\color{black}{1≤n,q≤10^5}\ $
  • $\color{black}{0≤k≤3}\ $
  • $\color{black}{1≤t_i≤10^9}\ $
  • $\color{black}{1≤l≤r≤n}\ $
輸出說明

對於每個操作 $\color{black}{2}\ $，輸出計算結果。

因為答案可能會很大，請 $\color{black}{mod\ (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 
100
52
39
100
41
範例輸入 #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 
18
55
64
46
63
77
63
範例輸入 #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 
66
69
96
85
85
70
28
67
測資資訊：
記憶體限制： 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
提示 ：

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

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

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

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

$\color{black}{10\%：q≤10^3}\ $

$\color{black}{10\%：n≤10^3}\ $

$\color{black}{80\%：無特別限制}\ $

標籤:
BIT 差分
出處:
Caido [管理者： becaido (Caido) ]

本題狀況 本題討論 排行

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