Wow! Such Sequence! （线段树） hdu4893

  2 // hehe
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cstdio>
  6 #include <queue>
  7 #include <stack>
  8 #include <vector>
  9 #include <map>
 10 #include <cmath>
 11 #include <set>
 12 #include <iostream>
 13 #include <string>
 14 using namespace std;
 15 #define LL __int64
 16 const int MAX = 1e6+10;
 17 const LL inf = 1LL<<62;
 18 LL sum[MAX<<2],col[MAX<<2],fib_sum[MAX<<2],fib[MAX];
 19 int cur=2;
 20 void init() {
 21     fib[1]=fib[0]=1;
 22     for(int i=2;i<MAX;i++) {
 23         if(fib[i-1]+fib[i-2]>inf) break;
 24         fib[i]=fib[i-1]+fib[i-2];
 25         cur++;
 26     }
 27     return ;
 28 }
 29 void push_up(int o) {
 30     fib_sum[o]=fib_sum[o<<1]+fib_sum[o<<1|1];
 31     sum[o]=sum[o<<1]+sum[o<<1|1];
 32 }
 33 void push_down(int o) {
 34     if(col[o]!=-1) {
 35         col[o<<1]=col[o<<1|1]=col[o];
 36         sum[o<<1]=fib_sum[o<<1];
 37         sum[o<<1|1]=fib_sum[o<<1|1];
 38         col[o]=-1;
 39     }
 40     return;
 41 }
 42 void build(int L,int R,int o) {
 43     if(L==R) {
 44         sum[o]=0;
 45         fib_sum[o]=1; col[o]=-1;
 46         return ;
 47     }
 48     int mid=(L+R)>>1;
 49     build(L,mid,o<<1);
 50     build(mid+1,R,o<<1|1);
 51     push_up(o);
 52 }
 53 void add(int L,int R,int o,int k,int val) {
 54     if(L==R) {
 55         sum[o]+=(LL)val;
 56         int x=(int)(lower_bound(fib,fib+cur,sum[o])-fib);
 57 //        printf("%I64d %I64d\n",fib[x],fib[x-1]);
 58 //        printf("%I64d\n",sum[o]);
 59 
 60         if(x==0) fib_sum[o]=fib[x];
 61         else if((-fib[x]+sum[o])>=(-fib[x-1]+sum[o])) fib_sum[o]=fib[x-1];
 62         else fib_sum[o]=fib[x];
 63        // printf("%I64d\n",fib_sum[o]);
 64         return ;
 65     }
 66     push_down(o);
 67     int mid=(L+R)>>1;
 68     if(k<=mid) add(L,mid,o<<1,k,val);
 69     else add(mid+1,R,o<<1|1,k,val);
 70     push_up(o);
 71 }
 72 
 73 void Update(int L,int R,int o,int ls,int rs) {
 74     if(ls<=L&&rs>=R) {
 75         sum[o]=fib_sum[o];
 76         col[o]=1;
 77         return ;
 78     }
 79     push_down(o);
 80     int mid=(L+R)>>1;
 81     if(ls<=mid) Update(L,mid,o<<1,ls,rs);
 82     if(rs>mid) Update(mid+1,R,o<<1|1,ls,rs);
 83     push_up(o);
 84 }
 85 LL Query(int L,int R,int o,int ls,int rs) {
 86     if(ls<=L&&rs>=R) {
 87         return sum[o];
 88     }
 89     push_down(o);
 90     int mid=(L+R)>>1;
 91     LL res=0;
 92     if(ls<=mid) res+=Query(L,mid,o<<1,ls,rs);
 93     if(rs>mid) res+=Query(mid+1,R,o<<1|1,ls,rs);
 94     return res;
 95 
 96 }
 97 int main() {
 98     int n,m,op,ls,rs;
 99     init();
100     while(scanf("%d %d",&n,&m)==2) {
101         build(1,n,1);
102         for(int i=0;i<m;i++) {
103             scanf("%d %d %d",&op,&ls,&rs);
104             if(op==1) {
105                 add(1,n,1,ls,rs);
106             }
107             else if(op==2) {
108                 printf("%I64d\n",Query(1,n,1,ls,rs));
109             }
110             else {
111                 Update(1,n,1,ls,rs);
112             }
113         }
114     }
115     return 0;