1 1 2 1 1 5 4 1 1 7 1 3 17 3 2 4 2 1 5
0 22
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int LL;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=110000;
LL sum[maxn<<2],fibsum[maxn<<2],fib[100];
bool cov[maxn<<2];
void GET_FIB()
{
fib[0]=fib[1]=1LL;
for(int i=2;i<100;i++)
fib[i]=fib[i-1]+fib[i-2];
}
LL CHANGE(LL x)
{
int mark=-1;LL mx=99999999999LL;
for(int i=0;i<100;i++)
{
if(abs(x-fib[i])<mx)
{
mx=abs(x-fib[i]); mark=i;
}
}
return fib[mark];
}
void push_up(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
fibsum[rt]=fibsum[rt<<1]+fibsum[rt<<1|1];
}
void push_down(int l,int r,int rt)
{
if(l==r) return ;
if(cov[rt])
{
sum[rt<<1]=fibsum[rt<<1];
sum[rt<<1|1]=fibsum[rt<<1|1];
cov[rt<<1]=cov[rt<<1|1]=cov[rt];
cov[rt]=0;
}
}
void build(int l,int r,int rt)
{
sum[rt]=0,fibsum[rt]=1,cov[rt]=0;
if(l==r) return ;
int m=(l+r)/2;
build(lson); build(rson);
push_up(rt);
}
void ADD(int Kth,LL d,int l,int r,int rt)
{
push_down(l,r,rt);
if(l==r)
{
sum[rt]+=d;
fibsum[rt]=CHANGE(sum[rt]);
return ;
}
int m=(l+r)/2;
if(Kth<=m) ADD(Kth,d,lson);
else ADD(Kth,d,rson);
push_up(rt);
}
LL query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
push_down(l,r,rt);
int m=(l+r)/2;
LL ret=0;
if(L<=m) ret+=query(L,R,lson);
if(R>m) ret+=query(L,R,rson);
return ret;
}
void C_F(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
cov[rt]=1;
sum[rt]=fibsum[rt];
return ;
}
push_down(l,r,rt);
int m=(l+r)/2;
if(L<=m) C_F(L,R,lson);
if(R>m) C_F(L,R,rson);
push_up(rt);
}
int main()
{
int n,m;
GET_FIB();
while(scanf("%d%d",&n,&m)!=EOF)
{
build(1,n,1);
LL a,b,c;
while(m--)
{
scanf("%I64d%I64d%I64d",&a,&b,&c);
if(a==1)
ADD(b,c,1,n,1);
else if(a==2)
printf("%I64d\n",query(b,c,1,n,1));
else if(a==3)
C_F(b,c,1,n,1);
}
}
return 0;
}
HDOJ 4893 Wow! Such Sequence!,布布扣,bubuko.com
原文：http://blog.csdn.net/ck_boss/article/details/38294079