比赛时太大意，斐波拉契数列开小了。
题目大意：1个序列，3种操作，改变序列某个数大小，将序列中连续的一段每个数都变成其最近的斐波拉契数，以及查询序列中某一段的数之和。
解题思路：维护add[]数组表示线段树中每一段的需要改变到斐波拉契数的总和即可，color[]表示该段是否需要改变成斐波拉契，而当需要改变成斐波拉契数时，直接将sum+=add。其余便是线段树基础操作。
#include <cstdio> #define T 1000005 #define N 100005 long long f[81],sum[T],add[T]; int l,r,p; bool color[T]; void PushDown(int rt){ if(color[rt]){ color[rt]=0; color[rt*2]=color[rt*2+1]=1; sum[rt*2]+=add[rt*2]; sum[rt*2+1]+=add[rt*2+1]; add[rt*2]=0; add[rt*2+1]=0; } } void PushUp(int rt){ sum[rt]=sum[rt*2]+sum[rt*2+1]; add[rt]=add[rt*2]+add[rt*2+1]; } void build(int l, int r, int rt){ sum[rt]=0; color[rt]=0; if(l==r) add[rt]=1; if(l>=r) return; int m=(l+r)/2; build(l,m,rt*2); build(m+1,r,rt*2+1); PushUp(rt); } void update(int k, int d, int l, int r, int rt){ if(l==r){ color[rt]=0; sum[rt]+=d; if(sum[rt]<=0) add[rt]=1-sum[rt]; else{ for(int i=0; i<=64; i++) if(f[i]<=sum[rt]&&sum[rt]<f[i+1]){ if(sum[rt]-f[i]<=f[i+1]-sum[rt]) add[rt]=f[i]-sum[rt]; else add[rt]=f[i+1]-sum[rt]; break; } } return; } PushDown(rt); int m=(l+r)/2; if(k<=m) update(k,d,l,m,rt*2); else update(k,d,m+1,r,rt*2+1); PushUp(rt); } void change(int x, int y, int l, int r, int rt){ if(x<=l&&y>=r){ sum[rt]+=add[rt]; add[rt]=0; color[rt]=1; return; } PushDown(rt); int m=(l+r)/2; if(x<=m&&!color[rt*2]) change(x,y,l,m,rt*2); if(y>m&&!color[rt*2+1]) change(x,y,m+1,r,rt*2+1); PushUp(rt); } long long query(int x, int y, int l, int r, int rt){ if(x<=l&&y>=r) return sum[rt]; PushDown(rt); int m=(l+r)/2; long long s=0; if(x<=m) s+=query(x,y,l,m,rt*2); if(y>m) s+=query(x,y,m+1,r,rt*2+1); PushUp(rt); return s; } int main() { f[0]=f[1]=1; for(int i=2; i<=80; i++) f[i]=f[i-1]+f[i-2]; int n,m; while(scanf("%d%d",&n,&m)!=EOF){ build(1,n,1); for(int i=0; i<m; i++){ scanf("%d%d%d",&p,&l,&r); switch (p){ case 1: update(l,r,1,n,1); break; case 2: printf("%I64d\n",query(l,r,1,n,1)); break; case 3: change(l,r,1,n,1); break; } } } return 0; }
原文：http://www.cnblogs.com/Mathics/p/3876658.html
