首页 > 代码库 > hdu--4893--线段树
hdu--4893--线段树
这题的特点是 引入了个fib数组
其实就是 延迟更新的时候 换了个方式
<单点更新 区间求和 区间更新>
我觉得线段树的题目 不用什么解释 如果一下子没做出来 如果需要使用lazy的话 都是因为 不能很好地定义它的内容
lower_bound真心蛮好的 省去了自己手写二分 但也要看情况使用 = = 对了 它还有个兄弟叫做 upper_bound
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 typedef __int64 LL; 6 const int size = 100010; 7 const int num = 85; 8 LL fib[num+5]; 9 10 struct data 11 { 12 int L , R; 13 LL segSum , fibSum; 14 int flag; 15 }tree[size*4]; 16 17 void init( ) 18 { 19 fib[0] = fib[1] = 1; 20 for( int i = 2 ; i<num ; i++ ) 21 { 22 fib[i] = fib[i-1] + fib[i-2]; 23 } 24 } 25 26 LL find( LL var ) 27 { 28 int pos = lower_bound( fib , fib+num , var ) - fib; 29 if( !pos ) 30 return 1; 31 if( fib[pos]-var < var-fib[pos-1] ) 32 return fib[pos]; 33 return fib[pos-1]; 34 } 35 36 void pushDown( int rt ) 37 { 38 tree[rt].flag = 0; 39 tree[rt<<1].flag = tree[rt<<1|1].flag = 1; 40 tree[rt<<1].segSum = tree[rt<<1].fibSum; 41 tree[rt<<1|1].segSum = tree[rt<<1|1].fibSum; 42 } 43 44 void pushUp( int rt ) 45 { 46 tree[rt].segSum = tree[rt<<1].segSum + tree[rt<<1|1].segSum; 47 tree[rt].fibSum = tree[rt<<1].fibSum + tree[rt<<1|1].fibSum; 48 } 49 50 void build( int rt , int L , int R ) 51 { 52 int M = ( L + R ) >> 1; 53 tree[rt].L = L; 54 tree[rt].R = R; 55 tree[rt].flag = 0; 56 if( L==R ) 57 { 58 tree[rt].segSum = 0; 59 tree[rt].fibSum = 1; 60 return ; 61 } 62 build( rt<<1 , L , M ); 63 build( rt<<1|1 , M+1 , R ); 64 pushUp( rt ); 65 } 66 67 void update( int rt , int pos , LL var ) 68 { 69 int M = ( tree[rt].L + tree[rt].R ) >> 1; 70 if( tree[rt].L==pos && tree[rt].R==pos ) 71 { 72 tree[rt].segSum += var; 73 tree[rt].fibSum = find( tree[rt].segSum ); 74 return ; 75 } 76 if( tree[rt].flag ) 77 pushDown( rt ); 78 if( M>=pos ) 79 update( rt<<1 , pos , var ); 80 else 81 update( rt<<1|1 , pos , var ); 82 pushUp( rt ); 83 } 84 85 LL query( int rt , int L , int R ) 86 { 87 int M = ( tree[rt].L + tree[rt].R ) >> 1; 88 LL sum = 0; 89 if( tree[rt].L == L && tree[rt].R == R ) 90 { 91 return tree[rt].segSum; 92 } 93 if( tree[rt].flag ) 94 pushDown( rt ); 95 if( M>=R ) 96 sum += query( rt<<1 , L , R ); 97 else if( M+1<=L ) 98 sum += query( rt<<1|1 , L , R ); 99 else100 sum += query( rt<<1 , L , M ) + query( rt<<1|1 , M+1 , R );101 return sum;102 }103 104 void change( int rt , int L , int R )105 {106 int M = ( tree[rt].L + tree[rt].R ) >> 1;107 if( tree[rt].L == L && tree[rt].R == R )108 {109 tree[rt].segSum = tree[rt].fibSum;110 tree[rt].flag = 1;111 return ;112 }113 if( tree[rt].flag )114 pushDown( rt );115 if( M>=R )116 change( rt<<1 , L , R );117 else if( M+1<=L )118 change( rt<<1|1 , L , R );119 else120 {121 change( rt<<1 , L , M );122 change( rt<<1|1 , M+1 , R );123 }124 pushUp( rt );125 }126 127 int main()128 {129 cin.sync_with_stdio(false);130 init( );131 int n , m , op , L , R , pos;132 LL var , ans;133 while( cin >> n >> m )134 {135 build( 1 , 1 , n );136 while( m-- )137 {138 cin >> op;139 if( op==1 )140 {141 cin >> pos >> var;142 update( 1 , pos , var );143 }144 else if( op==2 )145 {146 cin >> L >> R;147 ans = query( 1 , L , R );148 cout << ans << endl;149 }150 else if( op==3 )151 {152 cin >> L >> R;153 change( 1 , L , R );154 }155 } 156 }157 return 0;158 }
today:
碎片时间
即使有着4维的空间 会不会因为我们习惯了3维而即使进入了4维而没有发觉呢
hdu--4893--线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。