题目链接：HDU4893-Wow! Such Sequence!

题意：

一个数列，三种操作：

1. x d：a[x]+=d
2. l r：求区间[l,r]的和
3. l r：让区间内的数变为最邻近的Fib数，若存在两个Fib数距离相等，取较小值。

题解：

线段树。

用fib记录最邻近的Fib数，cov记录区间是否全为Fib数。

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
int n, q;
ll sum[MAXN << 2], fib[MAXN << 2], Fib[102];
//sum记录区间和 fib记录最近的fib数 
int lazy[MAXN << 2];
bool cov[MAXN << 2];//记录区间是否全为fib数
void pushup(int rt)
{
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    cov[rt] = cov[rt << 1] & cov[rt << 1 | 1];
}
void pushdown(int l, int r, int rt)
{
    int mid = (l + r) >> 1;
    if (lazy[rt] != -1)
    {
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        sum[rt << 1] += (mid - l + 1) * lazy[rt];
        sum[rt << 1 | 1] += (r - mid) * lazy[rt];
        lazy[rt] = -1;
    }
    if (cov[rt])
    {
        cov[rt << 1] = cov[rt << 1 | 1] = cov[rt];
        //cov[rt] = 0;
    }
}
void build(int l, int r, int rt)
{
    lazy[rt] = -1;
    cov[rt] = 0;
    fib[rt] = 1;
    if (l == r)
    {
        sum[rt] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update_1(int L, int R, ll val, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        sum[rt] += val;
        lazy[rt] += val;

        int k = lower_bound(Fib, Fib + 91, sum[rt]) - Fib;
        if (sum[rt] == Fib[k] || sum[rt] == Fib[k - 1])
            cov[rt] = 1;
        else
            cov[rt] = 0;

        if (!cov[rt])
        {
            if (abs(Fib[k - 1] - sum[rt]) <= abs(Fib[k] - sum[rt]))
                fib[rt] = Fib[k - 1];
            else
                fib[rt] = Fib[k];
        }
        else
        {
            if (sum[rt] == Fib[k])
                fib[rt] = Fib[k];
            else
                fib[rt] = Fib[k - 1];
        }
        return;
    }
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        update_1(L, R, val, l, mid, rt << 1);
    if (R > mid)
        update_1(L, R, val, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update_2(int L, int R, int l, int r, int rt)
{
    if (cov[rt])
        return;
    if (L <= l && r <= R && l == r)
    {
        sum[rt] = fib[rt];
        cov[rt] = 1;
        return;
    }
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        update_2(L, R, l, mid, rt << 1);
    if (R > mid)
        update_2(L, R, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
ll query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return sum[rt];
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    ll res = 0;
    if (L <= mid)
        res += query(L, R, l, mid, rt << 1);
    if (R > mid)
        res += query(L, R, mid + 1, r, rt << 1 | 1);
    return res;
}
int main()
{
    Fib[0] = Fib[1] = 1;
    for (int i = 2; i <= 90; i++)
        Fib[i] = Fib[i - 1] + Fib[i - 2];
    while (scanf("%d%d", &n, &q) == 2)
    {
        build(1, n, 1);
        while (q--)
        {
            int op, l, r;
            scanf("%d%d%d", &op, &l, &r);
            if (op == 1)
                update_1(l, l, r, 1, n, 1);
            else if (op == 3)
                update_2(l, r, 1, n, 1);
            else
                printf("%lld\n", query(l, r, 1, n, 1));
        }
    }
    return 0;
}