比賽時太大意，斐波拉契數列開小了。

?

題目大意：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; } View Code

?

轉載于:https://www.cnblogs.com/Mathics/p/3876658.html

總結

以上是生活随笔為你收集整理的HDU 4893 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。