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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4893 Wow! Such Sequence!  

2014-07-30 16:56:37|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4893
多校合练第三场第7题。
n个数,初始值为0,有三种操作:
1:更新某个数;
2:区间求和;
3:区间内每个数换成离其最近的fib数。
线段树或者树状数组。
裸的树状数组会T,需要加优化,记录哪些数有被更新,这样第三步操作的时候,可以忽略很多。

int n,m;
LL f[N],num[N],c[N],fib[110]; //f[]用于树状数组记录,num[i]记录第i个数大小,c[i]记录离num[i]最近的fib数,fib[i]记录第i个fib数
set<int>newnum,ff; //newnum记录有更新数的坐标,ff临时记录哪些数被更新
set<int>::iterator it;

void init()
{
fib[0]=fib[1]=1;
for(int i=2;i<=91;i++)
fib[i]=fib[i-1]+fib[i-2];
}

int lowbit(int x){return x&-x;}

LL Sum(int x)
{
LL s=0;
while(x > 0)
{
s+=f[x];
x-=lowbit(x);
}
return s;
}

void Update(int x,LL y)
{
while(x <= n)
{
f[x]+=y;
x+=lowbit(x);
}
}

//二分查找离x最近的fib数
LL fun(LL x)
{
if(x == 0) return 1;
int pos=lower_bound(fib,fib+92,x)-fib;
LL t1=x-fib[pos-1],t2=fib[pos]-x;
return t1<=t2?fib[pos-1]:fib[pos];
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
init();
int a,lef,rig;
while(sf2(n,m)!=EOF)
{
MEM(f);MEM(num);
for(int i=0;i<=n;i++) c[i]=1;
newnum.clear();
for(int i=1;i<=n;i++) newnum.insert(i);
while(m--)
{
sf(a);
if(a == 1)
{
int k;
LL d;
scanf("%d %I64d",&k,&d);
Update(k,d);
num[k]+=d;
c[k]=fun(num[k]);
newnum.insert(k);
continue;
}
sf2(lef,rig);
if(a == 2)
pf64(Sum(rig)-Sum(lef-1));
else
{
ff.clear();
for(it=newnum.lower_bound(lef);it!=newnum.end();it++)
{
int t=*it;
if(!c[t]) continue; //如果c[t]==0,说明这个数没有被更新,继而不需要update了
if(t > rig) break;
if(num[t] != c[t]) Update(t,c[t]-num[t]);
num[t]=c[t];
c[t]=0;
ff.insert(t);
}
for(it=ff.begin();it!=ff.end();it++)
newnum.erase(*it);
}
}
}
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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