学步园

本题为一道线段树应用题，但区间更新略有不同。

同时维护两颗线段树，一颗存储原有数串及其区间和，另一颗存储原有数串的最近费波拉契数及这些费波拉契数的区间和。
每一次区间更新不必更新至最底层，直接将该要更新的区间和替换为费波拉契树相应位置的区间和。

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <assert.h>
#include <algorithm>
#define MAX 1234567890
#define MIN -1234567890
#define eps 1e-8

using namespace std;

const int maxn = 100100;
long long fibo[61];
long long sum[maxn<<2], rep[maxn<<2];
bool col[maxn<<2];

long long search_fibo(long long x, int l, int r)
{
        if(x <= 0) return 1;
        for(int i = 1; i < 60; i++)
        {
                if(fibo[i] <= x && fibo[i+1] >= x)
                {
                        long long ldis = x - fibo[i];
                        long long rdis = fibo[i+1] - x;
                        return ldis <= rdis ? fibo[i] : fibo[i+1];
                }
        }
}

void push_down(int rt)
{
        if(col[rt])
        {
                col[rt<<1] = col[rt<<1|1] = col[rt];
                sum[rt<<1] = rep[rt<<1];
                sum[rt<<1|1] = rep[rt<<1|1];
                col[rt] = false;
        }
}

void build(int l, int r, int rt)
{
        if(l == r)
        {
                rep[rt] = 1;
                return ;
        }
        int m = (l + r) >> 1;
        build(l, m, rt<<1);
        build(m+1, r, rt<<1|1);
        rep[rt] = rep[rt<<1] + rep[rt<<1|1];
}

void update_point(int p, int add, int l, int r, int rt)
{
        if(l == r)
        {
                sum[rt] += (long long)add;
//                cout << "sum[" << rt << "]: " << sum[rt] << endl;
                rep[rt] = search_fibo(sum[rt], 0, 60);
//                cout << "rep[" << rt << "]: " << rep[rt] << endl;
                return ;
        }
        push_down(rt);
        int m = (l + r) >> 1;
        if(p <= m) update_point(p, add, l, m, rt<<1);
        else update_point(p, add, m+1, r, rt<<1|1);
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
        rep[rt] = rep[rt<<1] + rep[rt<<1|1];
}

void update_interval(int L, int R, int l, int r, int rt)
{
        if(L <= l && R >= r)
        {
                col[rt] = true;
                sum[rt] = rep[rt];
                return ;
        }
        push_down(rt);
        int m = (l + r) >> 1;
        if(L <= m) update_interval(L, R, l, m, rt<<1);
        if(R > m) update_interval(L, R, m+1, r, rt<<1|1);
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

long long query(int L, int R, int l, int r, int rt)
{
        if(L <= l && R >= r) return sum[rt];
        push_down(rt);
        int m = (l + r) >> 1;
        long long ret = 0;
        if(L <= m) ret += query(L, R, l, m, rt<<1);
        if(R > m) ret += query(L, R, m+1, r, rt<<1|1);
        return ret;
}

int main()
{
        #ifdef BellWind
        freopen("4893.in", "r", stdin);
        #endif // BellWind

        fibo[0] = fibo[1] = 1;
        for(int i = 2; i <= 60; i++) fibo[i] = fibo[i-1] + fibo[i-2];

        int n, m;
        while(~scanf("%d%d", &n, &m))
        {
                memset(sum, 0, sizeof(sum));
                memset(col, 0, sizeof(col));
                build(1, n, 1);

                while(m--)
                {
                        int op, a, b;
                        scanf("%d%d%d", &op, &a, &b);
                        if(op == 2) printf("%I64d\n", query(a, b, 1, n, 1));
                        if(op == 1) update_point(a, b, 1, n, 1);
                        if(op == 3) update_interval(a, b, 1, n, 1);
                }
        }

        return 0;
}