首页 > 代码库 > hdu-4893-Wow! Such Sequence!-线段树【2014多校第三场-J】

hdu-4893-Wow! Such Sequence!-线段树【2014多校第三场-J】

2024-07-14 23:23:29   220人阅读

题意：一个初始为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代码：

  1 #include<cstdio>  2 #include<iostream>  3 #include<algorithm>  4 using namespace std;  5 #define maxn 100005  6 #define lson l, m, rt<<1  7 #define rson m+1, r, rt<<1|1  8 long long sgt[maxn<<2], fib_num_sum[maxn<<2];  9 bool lazy[maxn<<2]; 10 long long fib[100]; 11 void init_fib() 12 { 13    fib[0] = fib[1] = 1; 14    for(int i = 2; i < 92; i++){ 15       fib[i] = fib[i-1] + fib[i-2]; 16    } 17 } 18  19 void push_up(int rt) 20 { 21    sgt[rt] = sgt[rt<<1] + sgt[rt<<1|1]; 22    fib_num_sum[rt] = fib_num_sum[rt<<1] + fib_num_sum[rt<<1|1]; 23 } 24  25 void push_down(int rt) 26 { 27    if(lazy[rt]){ 28       lazy[rt<<1] = lazy[rt<<1|1] = 1; 29       lazy[rt] = 0; 30       sgt[rt<<1] = fib_num_sum[rt<<1]; 31       sgt[rt<<1|1] = fib_num_sum[rt<<1|1]; 32    } 33 } 34  35 long long find_fib(long long x) 36 { 37    int a = lower_bound(fib, fib+92, x) - fib; 38    if(x && fib[a] - x >= x - fib[a-1]) return fib[a-1]; 39    return fib[a]; 40 } 41  42 void build(int l, int r, int rt) 43 { 44    lazy[rt] = 0, fib_num_sum[rt] = 1; 45    if(l == r){ 46       sgt[rt] = 0; 47       return; 48    } 49    int m = (r + l) >>1; 50    build(lson); 51    build(rson); 52    push_up(rt); 53 } 54 void add(int l, int r, int rt, int k, int d) 55 { 56    if(l == r) { 57       sgt[rt] += d; 58       fib_num_sum[rt] = find_fib(sgt[rt]); 59       return; 60    } 61    push_down(rt); 62    int m = (l+r)>>1; 63    if(m >= k) add(lson, k, d); 64    if(m < k) add(rson, k, d); 65    push_up(rt); 66 } 67  68 void change(int l, int r, int rt, int L, int R) 69 { 70    if(L <= l&&r <= R){ 71       lazy[rt] = 1; 72       sgt[rt] = fib_num_sum[rt]; 73       return; 74    } 75    push_down(rt); 76    int m = (r+l)>>1; 77    if(L <= m) change(lson, L, R); 78    if(m < R) change(rson, L, R); 79    push_up(rt); 80 } 81  82 long long query(int l, int r, int rt, int L, int R) 83 { 84    if(L <= l&&r <= R) return sgt[rt]; 85    push_down(rt); 86    int m = (r+l)>>1; 87    long long ans = 0; 88    if(L <= m) ans += query(lson, L, R); 89    if(m < R) ans += query(rson, L, R); 90    return ans; 91 } 92  93 int n, m; 94 void work() 95 { 96    build(1, n, 1); 97    while(m--){ 98       int a; scanf("%d", &a); 99       if(a == 1) {100          int k, d; scanf("%d%d", &k, &d);101          add(1, n, 1, k, d);102       }103       if(a == 2) {104          int l, r; scanf("%d%d", &l, &r);105          printf("%I64d\n", query(1, n, 1, l, r));106       }107       if(a == 3) {108          int l, r; scanf("%d%d", &l, &r);109          change(1, n, 1, l, r);110       }111    }112 }113 114 int main()115 {116    init_fib();117    while(scanf("%d%d", &n, &m) != EOF) work();118    return 0;119 }
View Code

 


联系
我们