题目大意
给出一个序列a[1..n]
q个询问形如”l r x y”问a[l..r]中 a[i]modx=y 的个数
1≤n,a[i]≤40000
题解
对于 x≤200 ，将a[]分成 n√ 块，预处理 s[i][x][y] 表示前i块中模x等于y的数的个数，然后询问时可以直接用s和暴力查询多出的部分，一次询问的时间复杂度为 O(n√)
对于 x≥200 ，那么满足 tmodx=y 的不同的t的个数最多只有 40000x ，那么这一部分可以使用Mo’s algorithm，用桶来维护每种值出现的次数，然后询问时就直接询问，一次询问的复杂度是 O(n√)
总的时间复杂度是 O((n+q)n√)
Code
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;typedef long long LL;
typedef double db;const int N = 40010;
const int blk = 200;int get(){char ch;while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');if (ch=='-'){int s=0;while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';return -s;}int s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';return s;
}int s1[blk+10][blk+10][blk+10];
int s2[N];
int n,q,a[N],q1,mv;
int bl[N];
struct query{int id,l,r,x,y;friend bool operator < (query a,query b){if (bl[a.l]!=bl[b.l])return bl[a.l]<bl[b.l];return a.r<b.r;}
}t[N];
int ans[N];int getv(int w,int x,int y){if (w==0)return 0;int v=s1[x][bl[w]-1][y];fo(i,(bl[w]-1)*blk+1,w)if (a[i]%x==y)v++;return v;
}void solve(){sort(t+1,t+1+q1);int l=1,r=0;fo(i,1,q1){while(l<t[i].l)s2[a[l++]]--;while(l>t[i].l)s2[a[--l]]++;while(r>t[i].r)s2[a[r--]]--;while(r<t[i].r)s2[a[++r]]++;fo(j,0,mv/t[i].x)if (j*t[i].x+t[i].y<=40000)ans[t[i].id]=ans[t[i].id]+s2[j*t[i].x+t[i].y];}
}int main(){n=get();q=get();fo(i,1,n){a[i]=get();mv=max(mv,a[i]);}fo(i,1,n)bl[i]=(i-1)/blk+1;int tp=bl[n];fo(x,1,blk){fo(i,1,n)s1[x][bl[i]][a[i]%x]++;fo(i,1,tp)fo(j,0,x-1)s1[x][i][j]+=s1[x][i-1][j];}fo(i,1,q){int l=get()+1,r=get()+1,x=get(),y=get();if (x<=blk)ans[i]=getv(r,x,y)-getv(l-1,x,y);else{t[++q1].l=l;t[q1].r=r;t[q1].x=x;t[q1].y=y;t[q1].id=i;}}solve();fo(i,1,q)printf("%d\n",ans[i]);return 0;
}