HDU 4893 Wow! Such Sequence!(2014 Multi-University Training Contest 3)

题意:

有三种操作:

1 x y: 表示给x位置加上y

2 x y:查询【x,y】的区间和

3 x y:将 【x,y】 区间上的数变为最接近的 Fibonacci。

思路: 1 操作按正常单调更新,区间求和的操作。

2 操作按正常区间求和。

    3  如果是之前该区间未被 第三类操作操作过,则更新到底,如果之前已经被第三类操作操作过则直接返回。 这里要打一个标记,要注意 在第1类操作单点加时要把标记往下更新。

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include <iostream>
#define LL long long
#define debug(x) printf(#x"= %d\n",x);
#define N 100050
#define L(x) (x<<1)
#define R(x) (x<<1|1)
using namespace std;
int flag[N*];
LL sum[N*];
LL f[];
int fcnt;
void build(int l,int r,int i)
{
flag[i]=sum[i]=;
if(l!=r)
{
int mid=(l+r)>>;
build(l,mid,L(i));
build(mid+,r,R(i));
}
}
void pushdown(int i)
{
if(flag[i])
{
flag[L(i)]=flag[R(i)]=;
flag[i]=;
}
}
void pushup(int i)
{
sum[i]=sum[L(i)]+sum[R(i)];
}
void add(int l,int r,int p,int va,int i)
{
if(l==r)
{
sum[i]+=va;
flag[i]=;
return;
}
pushdown(i);
int mid=(l+r)>>;
if(p<=mid)add(l,mid,p,va,L(i));
else add(mid+,r,p,va,R(i));
pushup(i);
}
void update(int l,int r,int pl,int pr,int i)
{
if(l==r)
{
if(sum[i]<=){
sum[i]=;
}
else
{
int l=,r=fcnt;
while(r-l>)
{
int mid=(l+r>>);
if(f[mid]>=sum[i])r=mid;
else l=mid;
}
if(sum[i]-f[l]<=f[r]-sum[i])
sum[i]=f[l];
else
sum[i]=f[r];
}
//printf("::%d %I64d\n",l,sum[i]);
return;
}
if(flag[i])
return;
if(l>=pl&&r<=pr)
flag[i]=;
int mid=(l+r)>>;
if(pl<=mid)
update(l,mid,pl,pr,L(i));
if(pr>mid)
update(mid+,r,pl,pr,R(i));
pushup(i);
}
LL query(int l,int r,int pl,int pr,int i)
{
if(l>=pl&&r<=pr)
{
return sum[i];
}
int mid=(l+r)>>;
LL tmp=;
if(pl<=mid)tmp+=query(l,mid,pl,pr,L(i));
if(pr>mid)tmp+=query(mid+,r,pl,pr,R(i));
return tmp;
}
int main() {
f[]=f[]=;
for(int i=;;++i)
{
f[i]=f[i-]+f[i-];
if(f[i]>1e17)
{
fcnt=i;
break;
}
}
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int x,y,z;
build(,n,);
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
if(x==)
{
add(,n,y,z,);
}
else if(x==)
{
printf("%I64d\n",query(,n,y,z,));
}
else
{
update(,n,y,z,);
}
}
}
return ;
}
上一篇:【USACO 3.3.2】商品购物


下一篇:xcode 消除警告