c710. 分玩具 - 高中生程式解題系統

內容

在 $A ?$ 家中，有許多倉庫排成一列，每個倉庫都堆放著一種玩具。

今天 $A ?$ 決定送出一些玩具給鎮上的小孩。他打算將編號 $l$ 和 $r$ 之間倉庫的玩具都搬上貨車，卻隨即發現有些玩具無法平分。
於是他列出 $M$ 個送禮計畫，請你幫忙計算每個計畫能送出多少種玩具。

輸入說明

第一行為兩正整數 $N, M (1 \leq N, M \leq 300000)$ 分別代表倉庫和計畫的數量。

第二行為各個倉庫所堆放的玩具數量 $C_{1}, C_{2}, \dots, C_{i}, \dots, C_{N} (1 \leq C_{i} \leq N)$ 。

接下來 $M$ 行分別有三個正整數 $l, r, k (1 \leq l \leq r \leq N, 1 \leq k \leq N)$ 代表 $A ?$ 要送出 $l$ 號倉庫到 $r$ 號倉庫的禮物給 $k$ 個孩子。

輸出說明

依序輸出每個送禮計畫中有多少種玩具能被送出。

範例輸入 #1

範例輸出 #1

5
3
1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <10M
公開測資點#3 (10%): 1.0s , <10M
公開測資點#4 (10%): 2.0s , <10M
公開測資點#5 (10%): 2.0s , <10M
公開測資點#6 (10%): 2.0s , <10M
公開測資點#7 (10%): 2.0s , <10M
公開測資點#8 (10%): 2.0s , <10M
公開測資點#9 (10%): 2.0s , <10M

提示：

第一個計畫中，每一種玩具都能送出。
第二個計畫中，能送出倉庫編號 2, 4, 5 的玩具。
第三個計畫中，只有倉庫編號 3 的玩具能平分給 3 個小孩。

測資點 $0 \sim 1 : N, M \leq 1000$ 。
測資點 $2 \sim 3 : N, M \leq 100000, C_{i}, k \leq 100$ 。
測資點 $4 \sim 9 : N, M \leq 300000$ 。

期望空間複雜度為 $O (N + M)$ ，雖然本題並未嚴格限制。

2019/04/21 修改測資並重測。

標籤:

離線處理

出處:

[管理者： icube (!@#$%^&*()_...) ]

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