a342. TOI 2020/06 潛力組：高級料理

題目描述

餐廳把 N 個裝著食材的杉木盒由上往下堆疊。每位服務生最多搬運重量 A，且只能從當下最上層開始，連同其下方連續幾層一起搬走，不能跳過中間的盒子。

廚師會在指定盒子裡加入或取出食材，也會詢問目前最少需要幾位服務生，才能將整疊盒子搬完。請依序處理所有指令，回答每次詢問。原題說明不會發生服務生連最上面一個盒子及其食材都搬不動的情況，並保證詢問答案至多為 30。

輸入格式

第一行為 N、Q、A，分別代表盒子數、指令數及每位服務生的負重上限。接下來 N 行各有一個整數 G，依照從頂端到最底端的順序給出各盒初始重量。

隨後 Q 行為指令：

• 0：詢問目前最少服務生人數。
• 1 I D：在第 I 個盒子加入重量 D 的食材。
• 2 I D：從第 I 個盒子取出重量 D 的食材。

盒子從上至下編號 1 至 N。原題界限如下：1 ≤ N、Q ≤ 2×10^5，1 ≤ A ≤ 10^9，0 ≤ G ≤ A，1 ≤ I ≤ N，1 ≤ D ≤ A。

分組：10 分滿足 N、Q ≤ 10^3；30 分滿足 N ≤ 10^3、Q ≤ 10^5；60 分依完整限制。

輸出格式

每遇到指令 0，輸出一行，為搬完目前所有盒子所需的最少服務生人數。

範例 1 兩次詢問的各盒重量分別為 9、4、2 與 6、4、2，故答案為 2、1。範例 2 兩次詢問時的重量分別為 2、3 與 12、12，答案為 1、2。

原題待釐清事項

• 範例 2 出現 D=15，但 A=12，與文字界限 D≤A 不一致。加入後第一盒暫時重達 17，也使「不會搬不動最上盒」的保證是否只適用詢問時點不明。原樣保留輸入及限制。

本稿僅供待審，不自行修補以上規格。

範例 1

輸入：

3 5 12
2
2
2
1 1 7
1 2 2
0
2 1 3
0

輸出：

2
1

範例 2

輸入：

2 5 12
2
3
0
1 1 15
1 2 9
2 1 5
0

輸出：

1
2

來源

TOI 2020/06 練習賽潛力組〈高級料理〉。依官方原題 PDF 自行整理，所有範例均取自原件。

原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202006/Cuisine.pdf