[文章目录]
Description
给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问，每次询问给出l,r,p,k，问满足l<=i<=r且Ai mod p = k的值i的个数。0< n,m < =10^5，任意1<=i<=n满足Ai<=10^4，0< p<=10^4，0<=k< p。
关于模数根号分治，小于根号的直接维护前缀和，大于根号的莫队+桶，暴力扫桶统计答案即可。时间复杂度O(n√p+m√n+p√p)
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define pb push_back
#define N 101000
#define W 10100
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return re;
}
int n,m,tot,a[N],t[W],fna[N];
struct ques
{
int l,r,b,p,k,id;
}q[N];
bool cmp(ques x,ques y) {return x.b==y.b ? x.r<y.r : x.b<y.b;}
vector<ques>qv[110];
vector<int>ve[110];
int getans(int k,int l,int r)
{
return lower_bound(ve[k].begin(),ve[k].end(),r+1)-
lower_bound(ve[k].begin(),ve[k].end(),l);
}
int main()
{
n=read(); m=read();
int i,j,l,r,p,k,bl=sqrt(n)+1;
for(i=1;i<=n;++i) a[i]=read();
for(i=1;i<=m;++i)
{
l=read(); r=read(); p=read(); k=read();
if(p>100)
{
q[++tot].id=i; q[tot].l=l; q[tot].b=l/bl;
q[tot].r=r; q[tot].p=p; q[tot].k=k;
}
else qv[p].pb((ques){l,r,0,p,k,i});
}
for(i=1;i<=100;++i) if(qv[i].size())
{
for(j=1;j<=n;++j) ve[a[j]%i].pb(j);
for(j=qv[i].size()-1;~j;--j)
fna[qv[i][j].id]=getans(qv[i][j].k,qv[i][j].l,qv[i][j].r);
for(j=0;j<i;++j) ve[j].clear();
}
sort(q+1,q+tot+1,cmp);
for(l=1,r=0,i=1;i<=tot;++i)
{
while(r<q[i].r) t[a[++r]]++;
while(l>q[i].l) t[a[--l]]++;
while(r>q[i].r) t[a[r--]]--;
while(l<q[i].l) t[a[l++]]--;
for(j=q[i].k;j<=10000;j+=q[i].p) fna[q[i].id]+=t[j];
}
for(i=1;i<=m;++i) printf("%d\n",fna[i]);
return 0;
}