题意：
有三种操作：
1 x y： 表示给x位置加上y
2 x y：查询【x，y】的区间和
3 x y：将 【x，y】 区间上的数变为最接近的 Fibonacci。
思路： 1 操作按正常单调更新，区间求和的操作。
2 操作按正常区间求和。
3 如果是之前该区间未被 第三类操作操作过，则更新到底，如果之前已经被第三类操作操作过则直接返回。 这里要打一个标记，要注意 在第1类操作单点加时要把标记往下更新。
#include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include <iostream> #define LL long long #define debug(x) printf(#x"= %d ",x); #define N 100050 #define L(x) (x<<1) #define R(x) (x<<1|1) using namespace std; int flag[N*4]; LL sum[N*4]; LL f[1000]; int fcnt; void build(int l,int r,int i) { flag[i]=sum[i]=0; if(l!=r) { int mid=(l+r)>>1; build(l,mid,L(i)); build(mid+1,r,R(i)); } } void pushdown(int i) { if(flag[i]) { flag[L(i)]=flag[R(i)]=1; flag[i]=0; } } void pushup(int i) { sum[i]=sum[L(i)]+sum[R(i)]; } void add(int l,int r,int p,int va,int i) { if(l==r) { sum[i]+=va; flag[i]=0; return; } pushdown(i); int mid=(l+r)>>1; if(p<=mid)add(l,mid,p,va,L(i)); else add(mid+1,r,p,va,R(i)); pushup(i); } void update(int l,int r,int pl,int pr,int i) { if(l==r) { if(sum[i]<=1){ sum[i]=1; } else { int l=1,r=fcnt; while(r-l>1) { int mid=(l+r>>1); if(f[mid]>=sum[i])r=mid; else l=mid; } if(sum[i]-f[l]<=f[r]-sum[i]) sum[i]=f[l]; else sum[i]=f[r]; } //printf("::%d %I64d ",l,sum[i]); return; } if(flag[i]) return; if(l>=pl&&r<=pr) flag[i]=1; int mid=(l+r)>>1; if(pl<=mid) update(l,mid,pl,pr,L(i)); if(pr>mid) update(mid+1,r,pl,pr,R(i)); pushup(i); } LL query(int l,int r,int pl,int pr,int i) { if(l>=pl&&r<=pr) { return sum[i]; } int mid=(l+r)>>1; LL tmp=0; if(pl<=mid)tmp+=query(l,mid,pl,pr,L(i)); if(pr>mid)tmp+=query(mid+1,r,pl,pr,R(i)); return tmp; } int main() { f[1]=f[2]=1; for(int i=3;;++i) { f[i]=f[i-1]+f[i-2]; if(f[i]>1e17) { fcnt=i; break; } } int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int x,y,z; build(1,n,1); while(m--) { scanf("%d%d%d",&x,&y,&z); if(x==1) { add(1,n,y,z,1); } else if(x==2) { printf("%I64d ",query(1,n,y,z,1)); } else { update(1,n,y,z,1); } } } return 0; }