在 $\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
第一個計畫中，每一種玩具都能送出。
第二個計畫中，能送出倉庫編號 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 修改測資並重測。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||