【BZOJ2506】calc

Description

给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问，每次询问给出l,r,p,k，问满足l<=i<=r且Ai mod p = k的值i的个数。

Input

第一行两个正整数n和m。

第二行n个数，表示A1,A2,…,An。

以下m行，每行四个数分别表示l,r,p,k。满足1<=l<=r<=n。

Output

对于每个询问，输出一行，表示可行值i的个数。

Sample Input

5 2
1 5 2 3 7
1 3 2 1
2 5 3 0

Sample Output

2
1

HINT

数据范围：
0<n,m<=10^5，任意1<=i<=n满足Ai<=10^4，0<p<=10^4，0<=k<p。

题解：发现Ai很小，考虑分段处理询问。对于p<100的，直接用vector维护所有%p=k的位置，然后查询时在vector上二分即可。

对于p>100的呢？考虑莫队，用桶维护区间中所有数出现的次数，然后暴力查询，时间复杂度还是nsqrt(n)的。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <cmath>

using namespace std;

const int maxn=100010;

int n,m,tot,mx,B;

vector<int> s[110][110];

struct node

{

	int l,r,a,b,org;

}q[maxn];

int ans[maxn],v[maxn],st[maxn];

bool cmp(const node &a,const node &b)

{

	return (a.l/B==b.l/B)?(a.r<b.r):(a.l/B<b.l/B);

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd(),m=rd(),B=int(sqrt(double(n)));

	int i,j,l,r,a,b;

	for(i=1;i<=n;i++)

	{

		v[i]=rd(),mx=max(mx,v[i]);

		for(j=1;j<=100;j++)	s[j][v[i]%j].push_back(i);

	}

	for(i=1;i<=m;i++)

	{

		l=rd(),r=rd(),a=rd(),b=rd();

		if(a<=100)

		{

			ans[i]=upper_bound(s[a][b].begin(),s[a][b].end(),r)-lower_bound(s[a][b].begin(),s[a][b].end(),l);

		}

		else q[++tot].l=l,q[tot].r=r,q[tot].a=a,q[tot].b=b,q[tot].org=i;

	}

	sort(q+1,q+tot+1,cmp);

	for(l=q[1].l,r=l-1,i=1;i<=tot;i++)

	{

		while(l>q[i].l)	st[v[--l]]++;

		while(l<q[i].l)	st[v[l++]]--;

		while(r<q[i].r)	st[v[++r]]++;

		while(r>q[i].r)	st[v[r--]]--;

		for(j=q[i].b;j<=mx;j+=q[i].a)	ans[q[i].org]+=st[j];

	}

	for(i=1;i<=m;i++)	printf("%d\n",ans[i]);

	return 0;

}//5 2 1 5 2 3 7 1 3 2 1 2 5 3 0

巴特西

【BZOJ2506】calc 分段+vector+莫队