首页 > 代码库 > bzoj 2506 calc 题解
bzoj 2506 calc 题解
【原题】
2506: calc
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 228 Solved: 112
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。
【分析】初看题目我猜是神题,于是匆匆想去看题解。后来后悔自己没有仔细想!
解法是离线的,而且很巧妙。首先,把问题的首端点排序。对于P,我们分成两类:<=100和>100。
如果是<=100,随便暴力即可。我们设f[i][j]记录到目前这个点,除以i余j的个数,然后ans累加即可。
如果是>100,可以得到一个奇妙的性质:因为最大的数是10000,所以最多只有101个数满足除以P余K。那么对于某个询问,我们可以暴力枚举每个W使得W%P=K。然后把W个数累加即可。
【代码】
#include<cstdio> #include<algorithm> #define N 100005 #define O 105 using namespace std; struct node{int x,p,k,g,id;}T[N*2],Q[N*2]; int data[N],ans[N],f[O][O],s[10005]; int n,m,i,j,L,R,K,P,t,q; inline int Read() { char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar()); int x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x; } bool cmp(node a,node b){return a.x<b.x;} void solve_small() { sort(T+1,T+t+1,cmp);int k=1; while (k<=t&&!T[k].x) k++; for (int i=1;i<=n;i++) { for (int j=1;j<=100;j++) f[j][data[i]%j]++; while (k<=t&&T[k].x==i) ans[T[k].id]+=T[k].g*f[T[k].p][T[k].k],k++; } } void solve_big() { sort(Q+1,Q+q+1,cmp);int k=1; while (k<=q&&!Q[k].x) k++; for (int i=1;i<=n;i++) { s[data[i]]++; while (k<=q&&Q[k].x==i) { int now=0; for (int j=Q[k].k;j<=10000;j+=Q[k].p) now+=s[j]; ans[Q[k].id]+=Q[k].g*now;k++; } } } int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) data[i]=Read(); for (i=1;i<=m;i++) { L=Read();R=Read();P=Read();K=Read(); if (P<=100) T[++t]=(node){L-1,P,K,-1,i},T[++t]=(node){R,P,K,1,i}; else Q[++q]=(node){L-1,P,K,-1,i},Q[++q]=(node){R,P,K,1,i}; } sort(Q+1,Q+m+1,cmp); solve_small(); solve_big(); for (i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。