1. 来点离线做法

【题目描述】

给定长度为 $n$ 的数列 $a$，$q$ 次查询，每次给出 $l,r,k$，求：

$$\sum_{i=l}^r\left\lfloor\frac{a_i}{k}\right\rfloor$$

【输入格式】

第一行两个数 $n,q$（$1\le n,q\le 10^5$）。

第二行 $n$ 个非负整数 $a_i$（$0\le a_i\le 10^5$）。

接下来 $q$ 行，每行三个数 $l,r,k$ 表示询问 $1\le l\le r\le n,1\le k\le 10^5$。

【输出格式】

$q$ 行，每行一个整数表示答案。

【样例输入】

10 5
7 6 5 4 5 2 1 7 2 3
4 9 5
5 6 3
1 2 6
2 10 9
6 8 1

【样例输出】

2
1
2
0
10

【样例说明】

无

【数据规模与约定】

题面里有。

【来源】

ICPC2026 河南省赛。