c710: 分玩具
標籤 : Factorization 離線處理
通過比率 : 44% (4 人 / 9 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-10-17 18:16

內容

在 $\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 (11%): 1.0s , <1M
公開 測資點#1 (11%): 1.0s , <1M
公開 測資點#2 (11%): 1.0s , <10M
公開 測資點#3 (11%): 1.0s , <10M
公開 測資點#4 (11%): 2.0s , <10M
公開 測資點#5 (11%): 2.0s , <10M
公開 測資點#6 (11%): 2.0s , <10M
公開 測資點#7 (11%): 2.0s , <10M
公開 測資點#8 (12%): 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 8: N, M \le 300000}$。

期望空間複雜度為 $\color{black}{O(N + M)}$。

標籤:
Factorization 離線處理
出處:
[編輯:
icube (迭)
]


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