「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
1 5 2 3 7
1 3 2 1
2 5 3 0
Sample Output
2
1
1
HINT
数据范围：
0<n,m<=10^5，任意1<=i<=n满足Ai<=10^4，0<p<=10^4，0<=k<p。
Source
题解
首先将所有询问离线，然后对于每个询问分成询问1-（l-1）以及1-r两部分
然后将这些询问按照右端点排序将元素逐个加入处理
询问分成两类
p<=100和p>100
第一种可以用f1[i][j]表示加入的元素对i取模余数为j的个数
第二种用f2[i]表示大小为i的数的个数，因为p>100
只要将f[k],f[k+p],f[k+2*p]……最多100个相加即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m,top,mx; int a[100005]; int f1[105][105],f2[100005]; int ans[2][100005]; struct data{int x,f,p,k,num;}q[200005]; inline bool cmp(data a,data b) {return a.x<b.x;} void add(int x) { for(int i=1;i<=100;i++) f1[i][x%i]++; f2[x]++; } int main() { n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(),mx=max(mx,a[i]); for(int i=1;i<=m;i++) { int l=read(),r=read(),p=read(),k=read(); q[++top].x=l-1;q[top].p=p;q[top].k=k;q[top].num=i; q[++top].x=r;q[top].p=p;q[top].k=k;q[top].num=i;q[top].f=1; } sort(q+1,q+top+1,cmp); int now=0; for(int i=1;i<=top;i++) { while(now<q[i].x){now++;add(a[now]);} int p=q[i].p,k=q[i].k; if(p<=100)ans[q[i].f][q[i].num]=f1[p][k]; else for(int j=k;j<=mx;j+=p) ans[q[i].f][q[i].num]+=f2[j]; } for(int i=1;i<=m;i++) printf("%d\n",ans[1][i]-ans[0][i]); return 0; } |
因为p>100
计数器 9320222
OI 课件=>
OI 课件=>
[…] Orz hzwer巨巨 […]