学步园

思路：我的思路比较简单，也没有lazy操作。就是该干嘛干嘛，每次修改了向上更新下而已。对于每个节点我设一个b值，代表它下面的那些值是否都已经是斐波那契数了，这样在3操作时如果已经是了，就不必再往下更新了。仔细想，其实复杂度不大的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int l,r;
    long long a;
    bool b;
}t[400000];
int n,m;
long long fei[100];
void build(int ll,int rr,int rot)
{
    t[rot].l=ll;t[rot].r=rr;
    t[rot].b=0;
    t[rot].a=0;
    if(ll==rr)return;
    int mid=(ll+rr)/2;
    build(ll,mid,rot<<1);
    build(mid+1,rr,rot<<1|1);
}
void add(int k,int d,int rot)
{
    if(k==t[rot].l&&k==t[rot].r)
    {
        t[rot].a+=d;
        t[rot].b=0;
        //cout<<"change "<<k<<"  "<<t[rot].a<<endl;
        return;
    }
    int mid=(t[rot].l+t[rot].r)/2;
    if(k<=mid)add(k,d,rot<<1);
    else add(k,d,rot<<1|1);
    t[rot].a=t[rot<<1].a+t[rot<<1|1].a;
    t[rot].b=0;
}
long long query(int ll,int rr,int rot)
{
    if(t[rot].l==ll&&t[rot].r==rr)return t[rot].a;
    int mid=(t[rot].l+t[rot].r)/2;
    if(rr<=mid)return query(ll,rr,rot<<1);
    else if(ll>mid)return query(ll,rr,rot<<1|1);
    else return query(ll,mid,rot<<1)+query(mid+1,rr,rot<<1|1);
}
long long go(long long x)
{
    if(x<=0)return 1ll;
    int w=lower_bound(fei+1,fei+90,x)-fei;
    if(fei[w]-x<x-fei[w-1])return fei[w];
    else return fei[w-1];
}
void update(int ll,int rr,int rot)
{
    //cout<<"up "<<t[rot].l<<" "<<t[rot].r<<endl;
    if(t[rot].l==ll&&t[rot].r==rr&&t[rot].b)return;
    if(t[rot].l==t[rot].r)
    {
        //cout<<"fei "<<ll<<"  from  "<<t[rot].a<<"  to  ";
        t[rot].a=go(t[rot].a);
        //cout<<t[rot].a<<endl;
        t[rot].b=1;
        return;
    }
    int mid=(t[rot].l+t[rot].r)/2;
    if(rr<=mid)update(ll,rr,rot<<1);
    else if(ll>mid)update(ll,rr,rot<<1|1);
    else
    {
        update(ll,mid,rot<<1);
        update(mid+1,rr,rot<<1|1);
    }
    t[rot].a=t[rot<<1].a+t[rot<<1|1].a;
    if(t[rot<<1].b&&t[rot<<1|1].b)t[rot].b=1;
    else t[rot].b=0;
}
int main()
{
    int l,r,u;
    fei[0]=1;fei[1]=1;
    for(int i=2;i<=90;i++)fei[i]=fei[i-2]+fei[i-1];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,n,1);
        while(m--)
        {
            scanf("%d%d%d",&u,&l,&r);
            if(u==1)add(l,r,1);
            else if(u==2)printf("%I64d\n",query(l,r,1));
            else update(l,r,1);
        }
    }
    return 0;
}