f992: 線上蛋糕學習
Tags : BIT 差分
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

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

Content

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

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

這裡的草莓很奇特,為一直排 $\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\ ]}\ $ 的草莓大小總和。

Input

第一行為 $\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}\ $
Output

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

因為答案可能會很大,請 $\color{black}{mod\ (10^6+3)}\ $ 再輸出。

Sample Input #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
Sample Output #1
100
52
39
100
41
Sample Input #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
Sample Output #2
66
25
41
Sample Input #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
Sample Output #3
18
55
64
46
63
77
63
Sample Input #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
Sample Output #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
Hint :

$\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\%:無特別限制}\ $

Tags:
BIT 差分
出處:
Caido [管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」