注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4902 Nice boat  

2014-07-31 20:33:35|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4902
多校合练第四场第6题。
题意:
有n个数,两种操作:1. 把区间里的数全换成某个数a;2. 把区间内大于x的数换成gcd(ai,x).
题解:
本题限时15s,n和询问次数都是10w。可以用线段树解决,但是比赛时想到一个优化,没用线段树,直接400+MS过了。
先记录所有的询问,操作1放在一起,操作2放在一起。从第一个数开始,找到对该数操作的最后一次的操作1,然后从该操作往后看操作2,如果落在区间内,且大于x的则更新。
struct Node{
int
L,R,x;
}
node1[N],node2[N];
int
tot1,tot2,a[N],f[N];

int
Find(int x,int &y) //找到对x操作的最后一次操作1
{

for
(int i=tot1-1;i>=0;i--)
if
(x<=node1[i].R && x>=node1[i].L)
{

y=node1[i].x;
return
f[i];
}

y=-1;
return
0;
}


void
solve(int n)
{

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

int
pos,ans;
pos=Find(i,ans); //pos表示应从node2中哪个位置开始执行操作2
if
(ans == -1) ans=a[i];
for
(int j=pos;j<tot2;j++)
{

if
(ans > node2[j].x && i<=node2[j].R && i>=node2[j].L)
ans=gcd(ans,node2[j].x);
}

printf("%d ",ans);
}

pfn;
}


int
main()
{

#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
int T,n,aa,b,c,d,m;
sf(T);
while
(T--)
{

sf(n);
for
(int i=1;i<=n;i++) sf(a[i]);
sf(m);
tot1=0;tot2=0;
MEM(f);
for
(int i=0;i<m;i++)
{

scanf("%d%d%d%d",&aa,&b,&c,&d);
if
(aa == 1)
{

node1[tot1].L=b;
node1[tot1].R=c;
node1[tot1].x=d;
f[tot1]=tot2; //f[]相对于node1对node2的一个映射
tot1++;
}

else

{

node2[tot2].L=b;
node2[tot2].R=c;
node2[tot2++].x=d;
}
}

solve(n);
}

return
0;
}

  评论这张
 
阅读(47)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017