Wow! Such Sequence!
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4893
Description
```
Recently, Doge got a funny birthday present from his new friend, Protein Tiger from St. Beeze College. No, not cactuses. It's a mysterious blackbox.
After some research, Doge found that the box is maintaining a sequence an of n numbers internally, initially all numbers are zero, and there are THREE "operations":
1.Add d to the k-th number of the sequence.
2.Query the sum of ai where l ≤ i ≤ r.
3.Change ai to the nearest Fibonacci number, where l ≤ i ≤ r.
4.Play sound "Chee-rio!", a bit useless.
Let F0 = 1,F1 = 1,Fibonacci number Fn is defined as Fn = Fn - 1 + Fn - 2 for n ≥ 2.
Nearest Fibonacci number of number x means the smallest Fn where |Fn - x| is also smallest.
Doge doesn't believe the machine could respond each request in less than 10ms. Help Doge figure out the reason.
</big>
##Input
<big>
Input contains several test cases, please process till EOF.
For each test case, there will be one line containing two integers n, m.
Next m lines, each line indicates a query:
1 k d - "add"
2 l r - "query sum"
3 l r - "change to nearest Fibonacci"
1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, |d| < 231, all queries will be valid.
</big>
##Output
<big>
For each Type 2 ("query sum") operation, output one line containing an integer represent the answer of this query.
</big>
##Sample Input
<big>
1 1
2 1 1
5 4
1 1 7
1 3 17
3 2 4
2 1 5
</big>
##Sample Output
<big>
0
22
</big>
<br/>
##题意：
<big>
对一个数组进行若干操作:
1. 将A_k增加x.
2. 查询区间和.
3. 将区间内的数变成离它最近的斐波拉契数.
(注意这个斐波拉契数列是从 1 开始的!!!)
</big>
<br/>
##题解：
<big>
很容易想到用线段树维护，关键是如何操作3. 直接每个点维护复杂度太高.
如果一个数被操作3更新为了斐波那契数，那么再次更新时将不改变它的值. 利用这一点来剪枝.
对于树中的每个结点维护一个isfib标记, 表示当前结点所表示的区间内是否均为斐波那契数.
每次操作1更新时，将该点的isfib标志置0; (别忘了，WA了一次)
每次操作3更新时，若处理到某区间均为fib数则返回，否则一直向下处理到单点，并对单点进行更新.
</big>
<br/>
##代码：
``` cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <list>
#define LL long long
#define eps 1e-8
#define maxn 101000
#define mod 100000007
#define inf 0x3f3f3f3f
#define mid(a,b) ((a+b)>>1)
#define IN freopen("in.txt","r",stdin);
using namespace std;
LL fib[100];
int n;
struct Tree
{
int left,right;
LL sum;
bool isfib;
}tree[maxn<<2];
void pushup(int i) {
tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum;
tree[i].isfib = tree[i<<1].isfib && tree[i<<1|1].isfib ? 1 : 0;
}
void build(int i,int left,int right)
{
tree[i].left=left;
tree[i].right=right;
if(left==right){
tree[i].sum = 0;
tree[i].isfib = 0;
return ;
}
int mid=mid(left,right);
build(i<<1,left,mid);
build(i<<1|1,mid+1,right);
pushup(i);
}
void update(int i,int x,LL d)
{
if(tree[i].left == tree[i].right){
tree[i].sum += d;
tree[i].isfib = 0;
return;
}
int mid=mid(tree[i].left,tree[i].right);
if(x<=mid) update(i<<1,x,d);
else update(i<<1|1,x,d);
pushup(i);
}
LL find_fib(LL x) {
int pos = lower_bound(fib, fib+90, x) - fib;
if(!pos) return fib[pos];
if(abs(fib[pos]-x) < abs(fib[pos-1]-x)) return fib[pos];
return fib[pos-1];
}
void update_fib(int i,int left,int right)
{
if(tree[i].isfib) return ;
if(tree[i].left == tree[i].right)
{
tree[i].sum = find_fib(tree[i].sum);
tree[i].isfib = 1;
return ;
}
int mid=mid(tree[i].left,tree[i].right);
if(right<=mid) update_fib(i<<1,left,right);
else if(left>mid) update_fib(i<<1|1,left,right);
else {
update_fib(i<<1,left,mid);
update_fib(i<<1|1,mid+1,right);
}
pushup(i);
}
LL query(int i,int left,int right)
{
if(tree[i].left==left&&tree[i].right==right)
return tree[i].sum;
int mid=mid(tree[i].left,tree[i].right);
if(right<=mid) return query(i<<1,left,right);
else if(left>mid) return query(i<<1|1,left,right);
else return query(i<<1,left,mid)+query(i<<1|1,mid+1,right);
}
void init() {
fib[0] = 1; fib[1] = 1;
for(int i=2; i<90; i++) {
fib[i] = fib[i-1] + fib[i-2];
}
}
int main(int argc, char const *argv[])
{
//IN;
init();
int m;
while(scanf("%d %d", &n,&m) != EOF)
{
build(1, 1, n);
while(m--) {
int op, l, r;
scanf("%d %d %d", &op,&l,&r);
if(op == 1) {
update(1, l, (LL)r);
}
else if(op == 2) {
printf("%lld\n", query(1, l, r));
}
else if(op == 3) {
update_fib(1, l, r);
}
}
}
return 0;
}