http://www.zybbs.org/JudgeOnline/problem.php?id=2506

Rank1，这个故事告诉我们，桶排还是很快的……

找这道题题解的时候去了CXM大神的”题解“，然后果断被神犇们虐暴……最后根据题解里的提示自己YY出了这题……

一看这题木果断没感觉，然后感觉在线算法不行，果断想离线算法……

先把每次询问拆成1..l-1和1..r，离线后每次询问的就是A(1..x)中模p=k的数的个数。于是按照x排序，每次维护一个增量。

如果所有的p<=100，那这题就是水题了，维护一个s[i][j]表示模i为j的数的个数，然后每插入一个数a，则对于i=1..100，s[i][a%i]+=1

那么对于p>=100怎么办呢？考虑p>=100时有d个不同的数字模p=k：k,k+p,k+2p...k+(d-1)p，k+(d-1)p<=n，得到d<=101。

这说明，对于p>=100，最多只有101个不同的数字可能是答案！于是将每个数出现了几次记录下来，每次暴力找就行了。

#include <stdio.h>
char str[3000000],*p=str,*o=str;
int n,m,ans[200000],a[100000],in[200000][4],*ins[200000],s[101][100],u[10001],rka[100001],*rk=rka+1;
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}void print(x){
	char buf[5],*b=buf;
	if(!x)*o++=48;
	else{while(x)*b++=x%10+48,x/=10;
	while(b--!=buf)*o++=*b;}
	*o++='\n';
}main(){
	int i=-1,r,P,k,t=-1,max;fread(p,1,3000000,stdin);n=getint()-1;
	for(m=getint()<<1;i++!=n;a[i]=getint());
	for(i=-1;++i!=m;in[i][3]=i){
		rk[in[i][0]=getint()-2]++;r=getint()-1;in[i][1]=P=getint();in[i][2]=k=getint();in[i][3]=i;
		rk[in[++i][0]=r]++;in[i][1]=P;in[i][2]=k;
	}for(i=-1;i++!=n;rk[i]+=rk[i-1]);
	for(i=-1;++i!=m;ins[--rk[in[i][0]]]=in[i]);
	for(i=-1,max=0;++i!=m;){
		while(t<ins[i][0]){
			u[a[++t]]++;
			if(a[t]>max)max=a[t];
			for(k=0;k++!=100;s[k][a[t]%k]++);
		}if(ins[i][1]<=100)ans[ins[i][3]]=s[ins[i][1]][ins[i][2]];
		else for(k=ins[i][2]-ins[i][1];(k+=ins[i][1])<=max;)ans[ins[i][3]]+=u[k];
	}for(i=-2;(i+=2)!=m;)print(ans[i^1]-ans[i]);
	*--o=0;return puts(str),0;
}

• inline
• block