首页 > 代码库 > GDOI2014 吃(D1T3) 线段树
GDOI2014 吃(D1T3) 线段树
3644. 【GDOI2014】吃 (Standard IO)
Time Limits: 2000 ms Memory Limits: 262144 KB
用pre[][i][j]记录每个数离a[i]最近的(前/后)含有它的第j个因子的数。然后把询问排序离线处理，用线段树f[i]记录在范围之前/之后的数中与i的最大gcd
正着做一次统计(1-l-1,l-r)的maxgcd，反着做一次统计(l-r,r+1-n)的maxgcd即可
#include<cstdio>#include<cstdlib>#include<algorithm>#include<cmath>#include<cstring>using namespace std;int f[800111];int pre[2][100111][101],can[100111][101];int hash[100111];int n,m,tot,i,j,k,last;int ans[100111],a[100111];struct data{ int l,r,id;}q[100111];bool cmp(data a,data b){ return a.l<b.l;}bool cmp2(data a,data b){ return a.r>b.r;}void insert(int l,int r,int x,int y,int t){ int mid; if(l==r){ f[t]=max(f[t],y); return; } mid=(l+r)/2; if(x<=mid)insert(l,mid,x,y,t+t); if(x>mid)insert(mid+1,r,x,y,t+t+1); f[t]=max(f[t+t],f[t+t+1]);}int ask(int l,int r,int x,int y,int t){ int mid; if(l==x&&r==y)return f[t]; mid=(l+r)/2; if(y<=mid)return ask(l,mid,x,y,t+t); if(x>mid)return ask(mid+1,r,x,y,t+t+1); if(x<=mid&&y>mid)return max(ask(l,mid,x,mid,t+t),ask(mid+1,r,mid+1,y,t+t+1));}int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); memset(hash,0,sizeof(hash)); for(i=1;i<=n;i++){ tot=0; for(j=1;j<=(int)sqrt(a[i]);j++)if(a[i]%j==0){ tot++; pre[0][i][tot]=hash[j]; can[i][tot]=j; hash[j]=i; k=a[i]/j; if(j!=k){ tot++; can[i][tot]=k; pre[0][i][tot]=hash[k]; hash[k]=i; } } can[i][0]=tot; } memset(hash,0,sizeof(hash)); for(i=n;i>=1;i--){ tot=0; for(j=1;j<=(int)sqrt(a[i]);j++)if(a[i]%j==0){ tot++; can[i][tot]=j; pre[1][i][tot]=hash[j]; hash[j]=i; k=a[i]/j; if(k!=j){ tot++; can[i][tot]=k; pre[1][i][tot]=hash[k]; hash[k]=i; } } can[i][0]=tot; } scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+m,cmp); last=1; memset(f,0,sizeof(f)); for(i=1;i<=m;i++){ for(j=last;j<q[i].l;j++) for(k=1;k<=can[j][0];k++)if(pre[1][j][k])insert(1,n,pre[1][j][k],can[j][k],1); ans[q[i].id]=ask(1,n,q[i].l,q[i].r,1); last=q[i].l; } memset(f,0,sizeof(f)); sort(q+1,q+1+m,cmp2); last=n; for(i=1;i<=m;i++){ for(j=last;j>q[i].r;j--) for(k=1;k<=can[j][0];k++)if(pre[0][j][k])insert(1,n,pre[0][j][k],can[j][k],1); ans[q[i].id]=max(ans[q[i].id],ask(1,n,q[i].l,q[i].r,1)); last=q[i].r; } for(i=1;i<=m;i++)printf("%d\n",ans[i]);}
GDOI2014 吃(D1T3) 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。