【bzoj2506】calc

2014年5月28日1,8360

Description

         给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问,每次询问给出l,r,p,k,问满足l<=i<=r且Ai mod p = k的值i的个数。

Input

         第一行两个正整数n和m。
         第二行n个数,表示A1,A2,…,An。
         以下m行,每行四个数分别表示l,r,p,k。满足1<=l<=r<=n。

Output

         对于每个询问,输出一行,表示可行值i的个数。

Sample Input

5 2
1 5 2 3 7
1 3 2 1
2 5 3 0

Sample Output

2
1

HINT

数据范围:
0<n,m<=10^5,任意1<=i<=n满足Ai<=10^4,0<p<=10^4,0<=k<p。

Source

题解

首先将所有询问离线,然后对于每个询问分成询问1-(l-1)以及1-r两部分

然后将这些询问按照右端点排序将元素逐个加入处理

询问分成两类

p<=100和p>100

第一种可以用f1[i][j]表示加入的元素对i取模余数为j的个数

第二种用f2[i]表示大小为i的数的个数,因为p>100

只要将f[k],f[k+p],f[k+2*p]……最多100个相加即可

 

因为p>100