BZOJ 2506 calc

题目大意

给一个长度为$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;
}