补这题主要是因为第三个操作要维护区间, 而不是点, 否则会 T.
https://vjudge.net/problem/HDU-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 = 100050;
- int n, m;
- struct node
- {
- int l, r;
- LL sm1, sm2;
- bool t;
- } T[maxn <<2];
- LL F[150];
- void init()
- {
- F[0] = F[1] = 1;
- for(int i = 2; i <= 90; i++)
- F[i] = F[i - 1] + F[i - 2];
- }
- LL FBI(LL x)
- {
- int pos = (int)(lower_bound(F, F + 80, x) - F);
- if(!pos) return F[0];
- else
- {
- LL t1 = F[pos] - x;
- LL t2 = x - F[pos - 1];
- if(t1 < t2)
- return F[pos];
- else
- return F[pos - 1];
- }
- }
- void pushup(int id)
- {
- T[id].sm1 = T[id << 1].sm1 + T[id << 1 | 1].sm1;
- T[id].sm2 = T[id << 1].sm2 + T[id << 1 | 1].sm2;
- }
- void pushdown(int id)
- {
- if(T[id].t)
- {
- T[id << 1].sm1 = T[id << 1].sm2;
- T[id << 1].t = 1;
- T[id << 1 | 1].sm1 = T[id << 1 | 1].sm2;
- T[id << 1 | 1].t = 1;
- T[id].t = 0;
- }
- }
- void build(int id, int l, int r)
- {
- T[id].l = l;
- T[id].r = r;
- T[id].t = 0;
- if(l == r)
- {
- T[id].sm1 = 0;
- T[id].sm2 = 1;
- return ;
- }
- else
- {
- int mid = (l + r)>> 1;
- build(id <<1, l, mid);
- build(id << 1 | 1, mid + 1, 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)>> 1;
- if(r <= mid)
- return sum(id <<1, l, r);
- else if(l>= mid + 1)
- return sum(id <<1 | 1, l, r);
- else
- return sum(id << 1, l, mid) + sum(id << 1 | 1, mid + 1, 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 = 1;
- return ;
- }
- else
- {
- pushdown(id);
- int mid = (T[id].l + T[id].r)>> 1;
- if(r <= mid)
- {
- change(id <<1, l, r);
- }
- else if(l>= mid + 1)
- {
- change(id <<1 | 1, l, r);
- }
- else
- {
- change(id << 1, l, mid);
- change(id << 1 | 1, mid + 1, 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)>> 1;
- if(pos <= mid)
- update(id << 1, pos, d);
- else
- update(id << 1 | 1, pos, d);
- pushup(id);
- }
- }
- int main()
- {
- init();
- while(scanf("%d%d", &n, &m) != EOF)
- {
- build(1, 1, n);//
- LL d;
- int k, l, r, ty;
- for(int i = 1; i <= m; i++)
- {
- scanf("%d", &ty);
- if(ty == 1)
- {
- scanf("%d%lld", &k, &d);
- update(1, k, d);
- }
- else if(ty == 2)
- {
- scanf("%d%d", &l, &r);
- printf("%lld\n", sum(1, l, r));
- }
- else
- {
- scanf("%d%d", &l, &r);
- change(1, l, r);
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3203740.html