#P16710. Div

Div

题目描述

给定一个长度为 nn 的正整数序列 aa。

共有 QQ 次询问。每次询问给出三个整数 l,r,kl,r,k,你需要求出集合

$$\left\{ x\ \middle|\ \exists i\in[l,r],\ \left\lfloor\frac{a_i}{k}\right\rfloor=x, \ x>0 \right\}$$

中不同整数的个数。

输入格式

第一行输入两个正整数 n,Qn,Q,分别表示序列长度和询问次数。

第二行输入 nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 QQ 行,每行输入三个正整数 l,r,kl,r,k,表示一次询问。

输出格式

对每次询问输出一行一个整数,表示对应集合中不同正整数的数量。

样例

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

数据范围

对于所有测试数据:

  • 1≤n,Q≤2×1051\le n,Q\le 2\times 10^5;
  • 1≤ai≤n1\le a_i\le n;
  • 1≤l≤r≤n1\le l\le r\le n;
  • 1≤k≤n1\le k\le n。

原题各测试点规模如下:

测试点编号 n,Q≤n,Q\le
1∼21\sim2 2×1032\times10^3
3∼43\sim4 10410^4
5∼85\sim8 10510^5
9∼209\sim20 2×1052\times10^5