设为首页 加入收藏

TOP

hdu 4893 Wow! Such Sequence!
2015-07-20 17:59:52 来源: 作者: 【大 中 小】 浏览:2次
Tags：hdu 4893 Wow Such Sequence

?

?

三种操作：

1 k d - add
2 l r - query sum
3 l r - change to nearest Fibonacci

?

节点附件三个值：

s1:由lazy控制的区间的正确的和。

s2:区间内与所有数相近的fib数之和，随着单点更新而更新。

col:lazy,标记区间是否全部取fib数，是取1，否则取0。

询问区间的和时，找到相应区间直接返回s1,若有col为1的区间要先向下推送，表示要取该区间的fib数的和。

Mark.....

?

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) #define C 240 #define S 20 using namespace std; const int maxn = 100010; const int INF = 1 << 30; _LL fib[86]; void init() { fib[0] = fib[1] = 1; for(int i = 2; i <= 85; i++) fib[i] = fib[i-1] + fib[i-2]; } _LL Binsearch(_LL key) { int low = 0,high = 85; while(low <= high) { int mid = (low + high) >> 1; if(fib[mid] > key) high = mid-1; else low = mid+1; } if(fabs(fib[low]-key) < fabs(fib[high]-key)) return fib[low]; else return fib[high]; /*_LL Min = abs(fib[0]-key); int pos = 0; for(int i = 1; i <= 85; i++) { if(Min > abs(fib[i]-key)) { Min = abs(fib[i]-key); pos = i; } } return fib[pos];*/ } struct node { int l, r; LL s1,s2; int col; }tree[maxn*4]; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].col = 0; tree[v].s1 = 0; tree[v].s2 = r-l+1; if(l == r) { return; } int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); } void update_fib(int v, int l, int r) { if(tree[v].l == l && tree[v].r == r) { tree[v].col = 1; tree[v].s1 = tree[v].s2; return; } if(tree[v].col == 1) return; int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) update_fib(v*2,l,r); else if(l > mid) update_fib(v*2+1,l,r); else { update_fib(v*2,l,mid); update_fib(v*2+1,mid+1,r); } tree[v].s1 = tree[v*2].s1 + tree[v*2+1].s1; tree[v].s2 = tree[v*2].s2 + tree[v*2+1].s2; } void update(int v, int pos, _LL d) { if(tree[v].l == tree[v].r) { tree[v].s1 += d; tree[v].s2 = Binsearch(tree[v].s1); return; } if(tree[v].col == 1) { int mid = (tree[v].l + tree[v].r) >> 1; update_fib(v*2,tree[v].l,mid); update_fib(v*2+1,mid+1,tree[v].r); tree[v].col = 0; } int mid = (tree[v].l + tree[v].r) >> 1 ; if(pos <= mid) update(v*2,pos,d); else update(v*2+1,pos,d); tree[v].s1 = tree[v*2].s1 + tree[v*2+1].s1; tree[v].s2 = tree[v*2].s2 + tree[v*2+1].s2; } _LL query(int v, int l, int r) { if(tree[v].l == l && tree[v].r == r) { return tree[v].s1; } if(tree[v].col == 1) { int mid = (tree[v].l+tree[v].r)>>1; update_fib(v*2,tree[v].l,mid); update_fib(v*2+1,mid+1,tree[v].r); tree[v].col = 0; } int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) return query(v*2,l,r); else if(l > mid) return query(v*2+1,l,r); else return query(v*2,l,mid) + query(v*2+1,mid+1,r); } int main() { init(); int n,m; int num,l,r,pos; _LL d; while(~scanf(%d %d,&n,&m)) { build(1,1,n); while(m--) { scanf(%d,&num); if(num == 1) { scanf(%d %I64d,&pos,&d); update(1,pos,d); // for(int i = 1; i <= 3; i++) // printf(l : %2d r : %2d col : %2d s1 : %I64d s2 : %I64d ,tree[i].l,tree[i].r,tree[i].col,tree[i].s1,tree[i].s2); } else if(num == 2) { scanf(%d %d,&l,&r); printf(%I64d ,query(1,l,r)); } else { scanf(%d %d,&l,&r); update_fib(1,l,r); // for(int i = 1; i <= 3; i++) // printf(l : %2d r : %2d col : %2d s1 : %I64d s2 : %I64d ,tree[i].l,tree[i].r,tree[i].col,tree[i].s1,tree[i].s2); } } } return 0; }


?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：hdu 4908 BestCoder Sequence(计.. 下一篇：POJ 1465 Multiple (BFS，同余定..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: