題意：給定 n 個(gè)數(shù)的序列（1 <= n <= 100000，且初始均為 0），m 個(gè)操作（1 <= m <= 100000），操作共分三種：

1、將第 k 個(gè)數(shù)加 d；

2、求 l 到 r 區(qū)間和；

3、將 l 到 r 區(qū)間內(nèi)的數(shù)，各自變?yōu)榫嚯x各自最近的斐波那契數(shù)（如果有兩個(gè)數(shù)一樣近，則取小的斐波那契數(shù)）.

?

有區(qū)間求和區(qū)間修改還有點(diǎn)修改，很明顯的一個(gè)線段樹(shù)的題；

先將斐波那契數(shù)打表，然后每次查找時(shí)用 lower_bound 二分查找；

需要一個(gè) sum 數(shù)組用來(lái)求和，寫(xiě)兩個(gè) update 函數(shù)分別為某個(gè)點(diǎn)數(shù)值增加以及區(qū)間修改成斐波那契；

為了防止超時(shí)，還需要增加一個(gè)“判斷區(qū)間是否已經(jīng)成為斐波那契數(shù)”的判斷數(shù)組.

代碼如下：

#pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<list> #define fin freopen("in.txt", "r", stdin) #define fout freopen("out.txt", "w", stdout) #define pr(x) cout << #x << " : " << x << " " #define prln(x) cout << #x << " : " << x << endl #define Min(a, b) a < b ? a : b #define Max(a, b) a < b ? b : a typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const double pi = acos(-1.0); const double EPS = 1e-8; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const ll MOD = 1e9 + 7; using namespace std;#define NDEBUG #include<cassert> const int MAXN = 75 + 10; const int MAXT = 100000 + 10;ll fib[MAXN << 2];void init(){fib[0] = 1; fib[1] = 2;for(int i = 2; i < MAXN; ++i) fib[i] = fib[i - 1] + fib[i - 2]; }ll sum[MAXT << 2]; bool flag[MAXT << 2];ll getfib(ll value){int lur = lower_bound(fib, fib + MAXN, value) - fib;ll one = abs(fib[lur] - value);ll two = lur > 0 ? abs(fib[lur - 1] - value) : one;if(one != two) return one < two ? fib[lur] : fib[lur - 1];return lur > 0 ? fib[lur - 1] : fib[lur]; }void PushUp(int lur){sum[lur] = sum[lur << 1] + sum[lur << 1 | 1];flag[lur] = flag[lur << 1] & flag[lur << 1 | 1]; }void Update(int lur, int x, int l, int r, int id){if(l == r){sum[id] += x;flag[id] = false;return;}int mid = (l + r) >> 1;if(lur <= mid) Update(lur, x, l, mid, id << 1);else Update(lur, x, mid + 1, r, id << 1 | 1);PushUp(id); }void Update2(int L, int R, int l, int r, int id){if(flag[id]) return;if(l == r){sum[id] = getfib(sum[id]);flag[id] = true;return;}int mid = (l + r) >> 1;if(L <= mid) Update2(L, R, l, mid, id << 1);if(mid < R) Update2(L, R, mid + 1, r, id << 1 | 1);PushUp(id); }ll Query(int L, int R, int l, int r, int id){if(L <= l && r <= R){return sum[id];}int mid = (l + r) >> 1;ll ans = 0;if(L <= mid) ans += Query(L, R, l, mid, id << 1);if(mid < R) ans += Query(L, R, mid + 1, r, id << 1 | 1);return ans; }int main(){init();int n, m;while(scanf("%d%d", &n, &m) == 2){memset(sum, 0, sizeof sum);memset(flag, false, sizeof flag);while(m--){int o; scanf("%d", &o);if(o == 1){int k; int d;scanf("%d%d", &k, &d);Update(k, d, 1, n, 1);}else if(o == 2){int l, r;scanf("%d%d", &l, &r);printf("%I64d\n", Query(l, r, 1, n, 1));}else{int l, r;scanf("%d%d", &l, &r);Update2(l, r, 1, n, 1);}}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/tyty-TianTengtt/p/6048295.html

總結(jié)

以上是生活随笔為你收集整理的HDU 4893 - Wow! Such Sequence!（线段树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。