正文
hdu-4893-Wow! Such Sequence!-线段树【2014多校第三场-J】
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
题意：一个初始为0的数组，支持三种操作：1、向第k个数添加d,(|d| < 2^31);2、把[l, r]区间内的数字都换成与它最相近的Fibonacci数;3、询问[l, r]区间的和。
思路：初始化Fibonacci数组，longlong 类型内90个就够用了。
线段树区间查询，用lazy标记， sgt[]记录线段树各个节点的区间和， fib_num_sum[]记录与各个叶子节点当前值最接近的Fibonacci数，传递到区间fib_num_sum[]就是区间Fibonacci数的和。
操作1时第k个数的sgt[]+= d,同时更新fib_num_sum[]。操作2即把找到的区间sgt[]=fib_num_sum[]。操作3，直接返回区间sgt[]值。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100005
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
long long sgt[maxn<<], fib_num_sum[maxn<<];
bool lazy[maxn<<];
long long fib[];
void init_fib()
{
fib[] = fib[] = ;
for(int i = ; i < ; i++){
fib[i] = fib[i-] + fib[i-];
}
} void push_up(int rt)
{
sgt[rt] = sgt[rt<<] + sgt[rt<<|];
fib_num_sum[rt] = fib_num_sum[rt<<] + fib_num_sum[rt<<|];
} void push_down(int rt)
{
if(lazy[rt]){
lazy[rt<<] = lazy[rt<<|] = ;
lazy[rt] = ;
sgt[rt<<] = fib_num_sum[rt<<];
sgt[rt<<|] = fib_num_sum[rt<<|];
}
} long long find_fib(long long x)
{
int a = lower_bound(fib, fib+, x) - fib;
if(x && fib[a] - x >= x - fib[a-]) return fib[a-];
return fib[a];
} void build(int l, int r, int rt)
{
lazy[rt] = , fib_num_sum[rt] = ;
if(l == r){
sgt[rt] = ;
return;
}
int m = (r + l) >>;
build(lson);
build(rson);
push_up(rt);
}
void add(int l, int r, int rt, int k, int d)
{
if(l == r) {
sgt[rt] += d;
fib_num_sum[rt] = find_fib(sgt[rt]);
return;
}
push_down(rt);
int m = (l+r)>>;
if(m >= k) add(lson, k, d);
if(m < k) add(rson, k, d);
push_up(rt);
} void change(int l, int r, int rt, int L, int R)
{
if(L <= l&&r <= R){
lazy[rt] = ;
sgt[rt] = fib_num_sum[rt];
return;
}
push_down(rt);
int m = (r+l)>>;
if(L <= m) change(lson, L, R);
if(m < R) change(rson, L, R);
push_up(rt);
} long long query(int l, int r, int rt, int L, int R)
{
if(L <= l&&r <= R) return sgt[rt];
push_down(rt);
int m = (r+l)>>;
long long ans = ;
if(L <= m) ans += query(lson, L, R);
if(m < R) ans += query(rson, L, R);
return ans;
} int n, m;
void work()
{
build(, n, );
while(m--){
int a; scanf("%d", &a);
if(a == ) {
int k, d; scanf("%d%d", &k, &d);
add(, n, , k, d);
}
if(a == ) {
int l, r; scanf("%d%d", &l, &r);
printf("%I64d\n", query(, n, , l, r));
}
if(a == ) {
int l, r; scanf("%d%d", &l, &r);
change(, n, , l, r);
}
}
} int main()
{
init_fib();
while(scanf("%d%d", &n, &m) != EOF) work();
return ;
}
