题意：对于一个长度为n的序列进行m次操作(1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000)，有以下三种操作：
分析：线段树
#include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #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 int dr[] = {0, 0, -1, 1}; const int dc[] = {-1, 1, 0, 0}; const double pi = acos(-1.0); const double eps = 1e-8; const int MOD = 1e9 + 7; const int MAXN = 100000 + 10; const int MAXT = 10000 + 10; using namespace std; ll F[110]; ll sum[MAXN << 2]; bool flag[MAXN << 2]; int n, m; void add_up(int id){ sum[id] = sum[id << 1] + sum[id << 1 | 1]; flag[id] = flag[id << 1] & flag[id << 1 | 1]; } void add(int l, int r, int cur, ll x, int id){ if(l == r){ sum[id] += x; flag[id] = false; return; } int mid = (l + r) >> 1; if(cur <= mid){ add(l, mid, cur, x, id << 1); } else add(mid + 1, r, cur, x, id << 1 | 1); add_up(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(R >= mid + 1){ ans += query(L, R, mid + 1, r, id << 1 | 1); } return ans; } void get_Fibonacci(){ F[0] = 1; F[1] = 1; for(int i = 2; i < 80; ++i){ F[i] = F[i - 1] + F[i - 2]; } } void update(int L, int R, int l, int r, int id){ if(flag[id] == true){ return; } if(l == r){ ll tmp = lower_bound(F, F + 80, sum[id]) - F; if(sum[id] >= 4){ ll t1 = sum[id] - F[tmp - 1]; ll t2 = F[tmp] - sum[id]; if(t1 <= t2) --tmp; } sum[id] = F[tmp]; flag[id] = true; return; } int mid = (l + r) >> 1; if(L <= mid) update(L, R, l, mid, id << 1); if(R >= mid + 1) update(L, R, mid + 1, r, id << 1 | 1); add_up(id); } int main(){ get_Fibonacci(); while(scanf("%d%d", &n, &m) != EOF){ memset(sum, 0, sizeof sum); memset(flag, false, sizeof flag); while(m--){ int type; scanf("%d", &type); if(type == 1){ int k; ll d; scanf("%d%lld", &k, &d); add(1, n, k, d, 1); } if(type == 2){ int l, r; scanf("%d%d", &l, &r); ll ans = query(l, r, 1, n, 1); printf("%lld\n", ans); } if(type == 3){ int l, r; scanf("%d%d", &l, &r); update(l, r, 1, n, 1); } } } return 0; }