Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2067 Accepted Submission(s): 619
题意：
题目中说对一个长度为n，初始元素都为0的数组进行三种操作，如下：
1 k d 第 k 个元素加上 d
2 l r 求从 l 到 r 所有元素的和
3 l r 改变从 l 到 r 所有元素，都为原元素最近的 Fibonacci 数，差值相等时取较小值
思路：
对于第一个操作需要用到线段树中的单点更新操作，对于第二个操作需要用到线段树中的区 间求和操作，对于第三个操作需要思考一下，怎么处理才能最快地改变我们需要改变区间的状态。因为对于区间有个求和操作，那么我们会考虑到只需要改变一段区 间的和即可。处理的方案就是提前对每一段的 区间和 都找到相应的 Fibonacci 数作为映射，那么我们要对区间进行第三操作时，只需要将区间做一下标记，然后将这个映射值覆盖到原 区间和 即可。
注意点：
1.注意 pushdown 和 pushup 的使用。
2.注意当访问到叶子节点时最好是返回(return)，若不返回那么开大线段树的大小(原为4倍)也行。
3.注意杭电的输出为 %I64。#include <cstdio> #include <cmath> using namespace std; #define N 100010 struct node { int L, R; long long sum, vsum; int flag; } tree[N << 2]; long long ans; long long ffib(long long val) { long long x = 0, y = 1; int i; for (i = 0; i < 100; ++i) { y = x + y; x = y - x; if(y >= val) break; } if(fabs(y - val) < fabs(x - val)) return y; return x; } void pushUp(int root) { ///向上回溯 不断更新区间和 if(tree[root].L == tree[root].R) return; tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum; tree[root].vsum = tree[root << 1].vsum + tree[root << 1 | 1].vsum; } void pushDown(int root) { ///向下更新 falg==1更新的时候 if(tree[root].flag && tree[root].L == tree[root].R) { tree[root].sum = tree[root].vsum; ///.vsum 求和之后对应该点的Fri数 tree[root].flag = 0; ///遍历完了 return ; } if(tree[root].flag) { tree[root << 1].flag = tree[root << 1 | 1].flag = 1; tree[root << 1].sum = tree[root << 1].vsum; tree[root << 1 | 1].sum = tree[root << 1 | 1].vsum; tree[root].flag = 0; ///遍历完了 } } void build(int L, int R, int root) { ///建树 tree[root].L = L; tree[root].R = R; tree[root].flag = 0; if(L == R) { tree[root].sum = 0; tree[root].vsum = 1; return ; } int mid = (L + R) >> 1; build(L, mid, root << 1); build(mid + 1, R, root << 1 | 1); pushUp(root); ///递归遍历求和 } void add(int pos, int val, int root) { if (tree[root].L == tree[root].R) { tree[root].sum += val; tree[root].vsum = ffib(tree[root].sum); tree[root].flag = 0; return ; } pushDown(root); int mid = (tree[root].L + tree[root].R) >> 1; if (mid >= pos) add(pos, val, root << 1); else add(pos, val, root << 1 | 1); pushUp(root); } void update(int L, int R, int root) { if (L <= tree[root].L && R >= tree[root].R) { tree[root].flag = 1; tree[root].sum = tree[root].vsum; return ; } pushDown(root); int mid = (tree[root].L + tree[root].R) >> 1; if (mid >= R) update(L, R, root << 1); else if (mid + 1 <= L) update(L, R, root << 1 | 1); else { update(L, mid, root << 1); update(mid + 1, R, root << 1 | 1); } pushUp(root); } void query(int L, int R, int root) { if (L <= tree[root].L && R >= tree[root].R) { ans += tree[root].sum; return ; } pushDown(root); int mid = (tree[root].L + tree[root].R) >> 1; if (mid >= R) query(L, R, root << 1); else if (mid + 1 <= L) query(L, R, root << 1 | 1); else { query(L, mid, root << 1); query(mid + 1, R, root << 1 | 1); } pushUp(root); } int main(int argc, char *argv[]) { int n, m, i; int op, x, y; while(scanf("%d%d", &n, &m) != EOF) { build(1, n, 1); for (i = 0; i < m; ++i) { scanf("%d%d%d", &op, &x, &y); if(op == 1) { add(x, y, 1); } else if(op == 2) { ans = 0; query(x, y, 1); printf("%I64d\n", ans); // hdu } else if(op == 3) { update(x, y, 1); } } } return 0; }
HDU 4893 线段树的 点更新 区间求和,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhangying/p/3880206.html