题目：
街上的街灯亮起，指引向着远方的路。每个街灯上都有一个数，每次询问，第l个街灯到第r个街灯上的数模p等于v的有几个。
【输入格式】
第一行两个数N,M，代表街灯的个数和询问的个数。
接下来一行N个数，代表街灯上的数。
接下来M行，每行四个数l,r,p,v代表一组询问。
【输出格式】
对于每次询问，输出一行代表答案。
【样例输入】
5 2
1 5 2 3 7
1 3 2 1
2 5 3 0
【样例输出】
2
1
【数据规模与约定】
对于30%的数据，1≤N,M≤10^3。
对于另外30%的数据，每次询问的p一样。
对于100%的数据，1≤N,M≤10^5，街灯上的数不超过10^4，1≤p≤10^9。
题解：
首先会发现暴力就是n/k*logn的
我们注意到可以根号分块去做
对于k<=100的
我们预处理出f[i][j]表示模数是i，余数是j的数有哪些（用vector存）
对于k>100的每次查询根号nlogn
发现时间卡的比较紧。。
原题解说是可以用数组代替但我并不知道怎么用数组代替。。
二分查找的时候注意一下边界
数据出的比较水，0.1s都可以跑过
#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;++i) #define dep(i,t,h) for (rint i=t;i>=h;--i) const int N=2.1e5; int a[N],n,m,p,v,j; vector<int> ve[101][101],ve2[N]; char ss[1<<24],*A=ss,*B=ss; IL char gc() { return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++; } template<class T>void read(T &x) { rint f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48); while (c=gc(),c>47&&c<58) x=(x<<3)+(x<<1)+(c^48); x*=f; } #define v1 ve[p][v] #define v2 ve2[(j-1)*p+v] #define mid ((h+t)/2) #define mid2 ((h+t+1)/2) IL int query(int x,int l,int r) { if (x==1) { int h=0,t=v1.size()-1; if (t<0) return(0); while (h<t) { if (v1[mid]<l) h=mid+1; else t=mid; } if (v1[h]<l) h++; int ans1=h; h=0,t=v1.size()-1; while (h<t) { if (v1[mid2]>r) t=mid2-1; else h=mid2; } if (v1[h]>r) h--; return(h-ans1+1); } else { int h=0,t=v2.size()-1; if (t<0) return(0); while (h<t) { if (v2[mid]<l) h=mid+1; else t=mid; } if (v2[h]<l) h++; int ans1=h; h=0,t=v2.size()-1; while (h<t) { if (v2[mid2]>r) t=mid2-1; else h=mid2; } if (v2[h]>r) h--; return(h-ans1+1); } } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); read(n); read(m); int maxn=0; rep(i,1,n) read(a[i]),ve2[a[i]].push_back(i),maxn=max(maxn,a[i]); rep(i,1,100) rep(j,1,n) ve[i][a[j]%i].push_back(j); rep(i,1,m) { int h,t; read(h); read(t); read(p); read(v); if (p<=100) { printf("%d ",query(1,h,t)); } else { rint ans=0; for(j=1;j<=(maxn/p)+1;j++) { ans+=query(2,h,t); } printf("%d ",ans); } } return 0; }