HDU4893-线段树

题目给你三种操作：
1：将第i个数加上j；
2：求一个区间内数的和
3：将一个范围内的数改成与它最接近的斐波那契数，若距离两个相邻的数字距离一样取小的那个。
数组内所有数初始值为0
经典的线段树维护区间修改单点修改，区间查询。只要维护一个原数组和改变后的数组即可。区间更新的时侯直接赋值就可以了

Accode：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1);
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (int i = (n); i < (m); i++)
#define _rep(n,m,i) for (int i = (n); i <= (m); i++)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
LL T[N<<2], FT[N<<2];
LL f[100];
int lazy[N<<2];
void initF() {
  f[1] = f[0] = 1;
  for(int i = 2;i < 60; i++) {
    f[i] = f[i-1] + f[i-2];
  }
}
LL getnum(LL x) {
  int i = lower_bound(f,f+60,x) - f;
  if(i == 0) return 1;
  return f[i]-x >= x-f[i-1] ? f[i-1] : f[i];
}
void push_up(LL rt) {
  FT[rt] = FT[rt<<1] + FT[rt<<1|1];
  T[rt] = T[rt<<1] + T[rt<<1|1];
}
void push_down(LL rt) {
  lazy[rt<<1] = lazy[rt<<1|1] = 1;
  lazy[rt] = 0;
  T[rt<<1] = FT[rt<<1];
  T[rt<<1|1] = FT[rt<<1|1];
}
void build(LL rt, LL l, LL r) {
  if(l == r) {
    FT[rt] = 1;
    T[rt] = 0;
    lazy[rt] = 0;
    return ;
  }
  int mid = l + r >> 1;
  build(lson);
  build(rson);
  push_up(rt);
  lazy[rt] = 0;
}
void upd(LL rt, LL l, LL r, LL pos, LL x) {
  if(l == r) {
    T[rt] += x;
    FT[rt] = getnum(T[rt]);
    return ;
  }
  if(lazy[rt]) push_down(rt);
  int mid = l + r >> 1;
  if(pos <= mid) upd(lson, pos, x);
  else upd(rson, pos, x);
  push_up(rt);
}
void Fupd(LL rt, LL l, LL r, LL L, LL R) {
  if(l == L && R == r) {
    T[rt] = FT[rt];
    lazy[rt] = 1;
    return ;
  }
  if(lazy[rt]) push_down(rt);
  LL mid = l + r >> 1;
  if(R <= mid) Fupd(lson, L, R);
  else if(L > mid) Fupd(rson, L, R);
  else {
    Fupd(lson, L, mid);
    Fupd(rson, mid+1, R);
  }
  push_up(rt);
}
LL qry(LL rt, LL l, LL r, LL L, LL R) {
  if(l == L && r == R) {
    return T[rt];
  }
  if(lazy[rt]) push_down(rt);
  LL mid = l + r >> 1;
  if(R <= mid) return qry(lson, L, R);
  else if(L > mid) return qry(rson, L, R);
  else {
    return qry(lson, L, mid) + qry(rson, mid+1, R);
  }
}
int main() {
  initF();
  LL n, m, op, l, r;
  while(~scanf("%lld%lld", &n, &m)) {
    build(1,1,n);
    while(m--) {
      read(op);read(l);read(r);
      if(op == 1) upd(1,1,n,l,r);
      else if(op == 2) printf("%lld\n", qry(1,1,n,l,r));
      else Fupd(1,1,n,l,r);
    }
  }
}