首页 > 代码库 > HDU 4777 Rabbit Kingdom
HDU 4777 Rabbit Kingdom
素因子分解，树状数组。$ACM/ICPC$ $2013$杭州区域赛$H$题。
首先需要处理出数字$a[i]$左边最远到$L[i]$，右边最远到$R[i]$区间内所有数字都与$a[i]$互质。
那么对于左端点在$[L[i],i]$并且右端点在$[i,R[i]]$的询问，$a[i]$就可以作出一个贡献。
接下来的问题就可以转化为二维平面上有很多矩形，每次询问一个点被多少矩形覆盖。可以离线操作，类似于扫描线的思想做就可以了。
素因子分解需要一开始把$20$万个数字都处理好，避免每组测试数据内重复处理。
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<iostream>#include<queue>using namespace std;const int maxn=2e5+10;int w[maxn],n,q;struct X{ int x,y,ans,id;} s[maxn];struct OP{ int x,y1,y2;} add[maxn],del[maxn];bool com[maxn];int primes, prime[maxn],L[maxn],R[maxn];int pre[maxn];int c[maxn],hh;vector<int>Prime[maxn];int lowbit(int x) { return x&(-x); }void ADD(int p, int val) { while (p <= n) c[p] = c[p] + val, p = p + lowbit(p); }int sum(int p) { int r = 0; while (p > 0) r = r + c[p], p = p - lowbit(p); return r; }void update(int L, int R, int val) { ADD(L, val); ADD(R + 1, -val); }void solve(){ primes = 0; memset(com,false,sizeof(com)); com[0] = com[1] = true; for (int i = 2; i < maxn; ++i) { if (!com[i]) { prime[++primes] = i; } for (int j = 1; j <= primes && i*prime[j] < maxn; ++j) { com[i*prime[j]] = true; if (!(i % prime[j])) break; } } for(int i=2;i<=200000;i++) { int tp = i; for(int j=1;j<=primes&&tp!=1;j++) { if(tp%prime[j]) continue; Prime[i].push_back(prime[j]); while(!(tp%prime[j])) tp /= prime[j]; if(!com[tp]&&tp>1) { Prime[i].push_back(tp); break; } } }}bool cmp1(X a,X b) { return a.x<b.x; }bool cmp2(OP a,OP b) { return a.x<b.x; }bool cmp3(X a,X b) { return a.id<b.id; }int main(){ solve(); while(~scanf("%d%d",&n,&q)) { if(n==0&&q==0) break; for(int i=1; i<=n; i++) scanf("%d",&w[i]); for(int i=1; i<=q; i++) scanf("%d%d",&s[i].x,&s[i].y), s[i].id=i; sort(s+1,s+1+q,cmp1); for(int i=1;i<=200000;i++) pre[i]=0; for(int i=1;i<=n;i++) { if(w[i]==1) L[i]=1; else { L[i]=0; for(int j=0;j<Prime[w[i]].size();j++) { L[i]=max(L[i],pre[Prime[w[i]][j]]+1); pre[Prime[w[i]][j]]=i; } } } for(int i=1;i<=200000;i++) pre[i]=n+1; for(int i=n;i>=1;i--) { if(w[i]==1) R[i]=n; else { R[i]=n+1; for(int j=0;j<Prime[w[i]].size();j++) { R[i]=min(R[i],pre[Prime[w[i]][j]]-1); pre[Prime[w[i]][j]]=i; } } } int sz1=0,sz2=0; for(int i=1;i<=n;i++) { add[sz1].x=L[i]; add[sz1].y1=i; add[sz1].y2=R[i]; sz1++; del[sz2].x=i; del[sz2].y1=i; del[sz2].y2=R[i]; sz2++; } sort(add,add+sz1,cmp2); sort(del,del+sz2,cmp2); int idq=1,idadd=0,iddel=0; memset(c,0,sizeof c); for(int i=1;i<=n;i++) { while(idadd<sz1&&add[idadd].x==i) { update(add[idadd].y1,add[idadd].y2,1); idadd++; } while(idq<=q&&s[idq].x==i) { s[idq].ans=sum(s[idq].y); idq++; } while(iddel<sz2&&del[iddel].x==i) { update(del[iddel].y1,del[iddel].y2,-1); iddel++; } } sort(s+1,s+1+q,cmp3); for(int i=1;i<=q;i++) printf("%d\n",s[i].ans); } return 0;}
HDU 4777 Rabbit Kingdom
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。