c710: 分玩具
標籤 : 離線處理
通過比率 : 8人/16人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-04-21 12:48

內容

在 $\color{black}{A?}$ 家中,有許多倉庫排成一列,每個倉庫都堆放著一種玩具。

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

輸入說明

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

第二行為各個倉庫所堆放的玩具數量 $\color{black}{C_1, C_2, \cdots, C_i, \cdots, C_N \space (1 \le C_i \le N)}$。

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

輸出說明

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

範例輸入
5 3
1 2 3 2 2
1 5 1
1 5 2
1 5 3
範例輸出
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 個小孩。

測資點 $\color{black}{0 \sim 1: N, M \le 1000}$。
測資點 $\color{black}{2 \sim 3: N, M \le 100000, \space C_i, k \le 100}$。
測資點 $\color{black}{4 \sim 9: N, M \le 300000}$。

期望空間複雜度為 $\color{black}{O(N + M)}$,雖然本題並未嚴格限制。

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

標籤:
離線處理
出處:
[管理者:
icube (輸光光)
]


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