题意是这样的，给定一个n个元素的数组，初始值为0，3种操作：
1 k d将第k个数增加d；
2 l r 询问区间l...r范围内数之和；
3 l r 表示将区间l...r内的数变成离他最近的斐波那契数，要求尽量小。
线段树操作题目，其中对于第三种操作用一个懒惰标记一下，表示l...r内的数是不是已经变成斐波那契数，如果是的话，求和就是其相应数的斐波那契数之和。
代码：
//Template updates date: 20140718
#include <bits/stdc++.h>
#define esp 1e-6
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define pb push_back
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define lowbit(x) (x&(-x))
#define mp(a, b) make_pair((a), (b))
#define bit(k) (1<<(k))
#define iin freopen("pow.in", "r", stdin);
#define oout freopen("pow.out", "w", stdout);
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout);
#define bug puts("********))))))");
#define Inout iin oout
#define inout in out #define SET(a, v) memset(a, (v), sizeof(a))
#define SORT(a) sort((a).begin(), (a).end())
#define REV(a) reverse((a).begin(), (a).end())
#define READ(a, n) {REP(i, n) cin>>(a)[i];}
#define REP(i, n) for(int i = 0; i < (n); i++)
#define VREP(i, n, base) for(int i = (n); i >= (base); i--)
#define Rep(i, base, n) for(int i = (base); i < (n); i++)
#define REPS(s, i) for(int i = 0; (s)[i]; i++)
#define pf(x) ((x)*(x))
#define mod(n) ((n))
#define Log(a, b) (log((double)b)/log((double)a))
#define Srand() srand((int)time(0))
#define random(number) (rand()%number)
#define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a) using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<PII, int> VIII;
typedef VI:: iterator IT;
typedef map<string, int> Mps;
typedef map<int, int> Mpi;
typedef map<int, PII> Mpii;
typedef map<PII, int> Mpiii;
const int maxm = + ; LL f[];
int n, m;
LL sum[maxm<<], sum1[maxm<<], cover[maxm<<]; void pre() {
f[] = f[] = ;
Rep(i, , ) {
f[i] = f[i-] + f[i-];
}
}
void PushDown(int rt) {
if(cover[rt]) {
cover[rt] = ;
cover[rt<<] = cover[rt<<|] = ;
sum[rt<<] = sum1[rt<<];
sum[rt<<|] = sum1[rt<<|];
}
}
void PushUp(int rt) {
sum[rt] = sum[rt<<]+sum[rt<<|];
sum1[rt] = sum1[rt<<]+sum1[rt<<|];
}
void build(int l, int r, int rt) {
if(l == r) {
sum[rt] = ;
sum1[rt] = ;
cover[rt] = ;
return ;
}
int m = (l+r)>>;
build(lson);
build(rson);
PushUp(rt);
cover[rt] = ;
} void update(int l, int r, int rt, int k, int d) {
if(l == k && r == k) {
sum[rt] += d;
int b = upper_bound(f+, f+, sum[rt]) - f;
if(abs(f[b]-sum[rt]) >= abs(f[b-]-sum[rt]))
sum1[rt] = f[b-];
else
sum1[rt] = f[b];
return;
}
PushDown(rt);
int m = (l+r)>>;
if(k <= m)
update(lson, k, d);
else update(rson, k, d);
PushUp(rt);
}
void update1(int L, int R, int l, int r, int rt) {
if(L <=l && R >= r) {
cover[rt] = ;
sum[rt] = sum1[rt];
return;
}
PushDown(rt);
int m = (l+r)>>;
if(L <= m)
update1(L, R, lson);
if(R > m)
update1(L, R, rson);
PushUp(rt);
}
LL query(int L, int R, int l, int r, int rt) {
if(L <= l && R >= r) {
return sum[rt];
}
int m = (l+r)>>;
PushDown(rt);
LL ans = ;
if(L <= m)
ans += query(L, R, lson);
if( R > m)
ans += query(L, R, rson);
return ans;
}
int main() { pre();
while(scanf("%d%d", &n, &m) == ) {
build(, n, );
REP(i, m) {
int u, l, r;
scanf("%d%d%d", &u, &l, &r);
if(u == ) {
printf("%I64d\n", query(l, r, , n, ));
} else if(u == ) {
update(, n, , l, r);
} else {
update1(l, r, , n, );
}
}
}
return ;
}