题目大意

给一个长度为$n$的非负整数序列$A_1,A_2,…,A_n$。现有$m$个询问,每次询问给出$l,r,p,k$,问满足$l<=i<=r$且$A_i \mod p = k$的值$i$的个数。


某homework的时候学来的——看到mod想想根号分治。

对于$p \le \sqrt{A_i}$的询问,可以用vector记录$\mod i = j$的数的出现位置,对于询问二分即可。

对于$p \gt \sqrt{A_i}$的询问,可以用莫队+桶维护集合,查询的时候求出所有可能的$\mod i = j$的数,看看存不存在就OK了。

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,lim,v[100010],ans[100010],cnt[10010]={1};
vector<int>pos[110][110];
struct request{int l,r,p,k,id;}q[100010];
bool cmp(const request x,const request y)
{
    if(x.p<=100&&y.p>100) return false;
    if(x.p>100&&y.p<=100) return true;
    return x.l/lim==y.l/lim?x.r<y.r:x.l/lim<y.l/lim;
}
void movel(int x,int y)
{
    int i;
    if(x<y)
        for(i=x;i<y;++i)
            cnt[v[i]]--;
    if(x>y)
        for(i=x-1;i>=y;--i)
            cnt[v[i]]++;
}
void mover(int x,int y)
{
    int i;
    if(x<y)
        for(i=x+1;i<=y;++i)
            cnt[v[i]]++;
    if(x>y)
        for(i=x;i>y;--i)
            cnt[v[i]]--;
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    lim=sqrt(n);
    for(i=1;i<=n;++i)
    {
        scanf("%d",v+i);
        for(j=1;j<=100;++j) pos[j][v[i]%j].push_back(i);
    }
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].p,&q[i].k),q[i].id=i;
        if(q[i].p<=100)
            ans[i]=upper_bound(pos[q[i].p][q[i].k].begin(),pos[q[i].p][q[i].k].end(),q[i].r)-upper_bound(pos[q[i].p][q[i].k].begin(),pos[q[i].p][q[i].k].end(),q[i].l-1);
    }
    sort(q+1,q+m+1,cmp);
    for(i=1;i<=m;++i)
    {
        if(q[i].p<=100) break;
        movel(q[i-1].l,q[i].l),mover(q[i-1].r,q[i].r);
        for(j=q[i].k;j<=10000;j+=q[i].p) ans[q[i].id]+=cnt[j];
    }
    for(i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}