题目链接[http://acm.hdu.edu.cn/showproblem.php?pid=4893]
题意：输入n、q。表示有n个数，初始化默认这n个数都为零，有q次操作，操作种类分为三种：1、输入k,d,使得k位置的数加上d。2、输入l,r,求区间[l,r]的和并输出。3、输入l,r,把区间[l,r]内的数都改成斐波拉契数，修改方式为使得fabs[x-F[i]]最小，如果有多个F[i]满足情况，用最小的那个F[i]。1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, |d| < 231。
题解：对于前两种操作，可以用单点更新来维护，但是对于第三种操作如果用单点更新的话，会TLE(n^2)，所以我们要区间更新，我们要很快的知道区间[l,r]区间的FIB和，索性我们就在线段树里维护所有数的FIB和，在build,和操作一的时候更新就可以了。时间复杂度n*log(n)。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = ;
int n, m;
struct node
{
int l, r;
LL sm1, sm2;
bool t;
} T[maxn << ];
LL F[];
void init()
{
F[] = F[] = ;
for(int i = ; i <= ; i++)
F[i] = F[i - ] + F[i - ];
}
LL FBI(LL x)
{
int pos = (int)(lower_bound(F, F + , x) - F);
if(!pos) return F[];
else
{
LL t1 = F[pos] - x;
LL t2 = x - F[pos - ];
if(t1 < t2)
return F[pos];
else
return F[pos - ];
}
}
void pushup(int id)
{
T[id].sm1 = T[id << ].sm1 + T[id << | ].sm1;
T[id].sm2 = T[id << ].sm2 + T[id << | ].sm2;
}
void pushdown(int id)
{
if(T[id].t)
{
T[id << ].sm1 = T[id << ].sm2;
T[id << ].t = ;
T[id << | ].sm1 = T[id << | ].sm2;
T[id << | ].t = ;
T[id].t = ;
}
}
void build(int id, int l, int r)
{
T[id].l = l;
T[id].r = r;
T[id].t = ;
if(l == r)
{
T[id].sm1 = ;
T[id].sm2 = ;
return ;
}
else
{
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
pushup(id);
}
}
LL sum(int id, int l, int r)
{
if(T[id].l == l && T[id].r == r)
return T[id].sm1;
else
{
pushdown(id);
int mid = (T[id].l + T[id].r) >> ;
if(r <= mid)
return sum(id << , l, r);
else if(l >= mid + )
return sum(id << | , l, r);
else
return sum(id << , l, mid) + sum(id << | , mid + , r);
}
}
void change(int id, int l, int r)
{
if(T[id].l == l && T[id].r == r)
{
T[id].sm1 = T[id].sm2;
T[id].t = ;
return ;
}
else
{
pushdown(id);
int mid = (T[id].l + T[id].r) >> ;
if(r <= mid)
{
change(id << , l, r);
}
else if(l >= mid + )
{
change(id << | , l, r);
}
else
{
change(id << , l, mid);
change(id << | , mid + , r);
}
pushup(id);
}
}
void update(int id, int pos, LL d)
{
if(T[id].l == T[id].r)
{
T[id].sm1 += d;
T[id].sm2 = FBI(T[id].sm1);
return ;
}
else
{
pushdown(id);
int mid = (T[id].l + T[id].r) >> ;
if(pos <= mid)
update(id << , pos, d);
else
update(id << | , pos, d);
pushup(id);
}
}
int main()
{
init();
while(scanf("%d%d", &n, &m) != EOF)
{
build(, , n);//
LL d;
int k, l, r, ty;
for(int i = ; i <= m; i++)
{
scanf("%d", &ty);
if(ty == )
{
scanf("%d%lld", &k, &d);
update(, k, d);
}
else if(ty == )
{
scanf("%d%d", &l, &r);
printf("%lld\n", sum(, l, r));
}
else
{
scanf("%d%d", &l, &r);
change(, l, r);
}
}
}
return ;
}