bzoj 2506 calc 题解 - c++编程基础

【原题】

2506: calc

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 228 Solved: 112

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

【分析】初看题目我猜是神题，于是匆匆想去看题解。后来后悔自己没有仔细想！

解法是离线的，而且很巧妙。首先，把问题的首端点排序。对于P，我们分成两类：<=100和>100。

如果是<=100，随便暴力即可。我们设f[i][j]记录到目前这个点，除以i余j的个数，然后ans累加即可。

如果是>100，可以得到一个奇妙的性质：因为最大的数是10000，所以最多只有101个数满足除以P余K。那么对于某个询问，我们可以暴力枚举每个W使得W%P=K。然后把W个数累加即可。

【代码】

#include
  
   
#include
   
     #define N 100005 #define O 105 using namespace std; struct node{int x,p,k,g,id;}T[N*2],Q[N*2]; int data[N],ans[N],f[O][O],s[10005]; int n,m,i,j,L,R,K,P,t,q; inline int Read() { char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar()); int x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x; } bool cmp(node a,node b){return a.x