大黑為了加快烤披薩的進度，買了一個超大的魔法烤箱，能夠裝下$N$個披薩
為了防止披薩烤焦變成黑薩，大黑隨時需要一段區間內連續$K$個披薩烤的時間的最大總和來估計熟度
因為時間緊急，大黑從許多地方搜刮了$N$個二手披薩，因此每個披薩在開始時已經烤過$A_i$秒
身為他的得力助手，你需要完成大黑下的$M$個指示，指示有兩種:
1.將$[l, r]$區間內的所有披薩多烤$d$秒。
2.告訴大黑$[l, r]$區間內，連續$K$個披薩烤過的最大時間和，如果區間長度$<K$則輸出0。
請你在每筆第二種指示中輸出答案
若想只拿子題1、3的人請注意以下說明：
由於zerojudge只要看到一筆TLE就不會再繼續跑，所以你如果沒做處理的話，只會拿到子題1的分數。
處理方式可為下：
1.加入assert(n<=1000&&m<=1000)
2.特判(n>1000||m>1000)的case，若發生的話就不要做事
第一行數字$t$，代表總共有$t$筆測資
每筆測資中:
第一行爲$N$ $M$ $K$
第二行爲陣列$A$，總共有$N$個數字
接下來$M$行有兩種輸入，第一個是1或2的數字，代表選擇哪一種操作：
1 $l$ $r$ $d$ 對應到第一種操作
2 $l$ $r$ 對應到第二種操作
$1 \le N, M \le 2\times 10^5$
$1\leq K \leq min(10, N)$
$1 \le A_i , d \le 10^6 (1 \le i \le N)$
$1\leq l\leq r\leq N$
保證$t$筆測資中$N$和$M$總和 $\le 2\times 10^5$
輸出每個操作二的當下區間長度為 $K$ 的最大連續區間和
1 10 7 5 4 2 3 1 7 20 1 2 6 7 2 2 7 1 5 8 3 1 3 5 7 2 1 8 1 5 7 2 1 3 4 9 2 5 9
33 62 61
子題1:
$K=1, t筆測資中N和M總和\le 1000$
10分
子題2:
$K=1$
25分
子題3:
$t筆測資中N和M總和\le 1000$
35分
子題4:
原題
30分
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||