首页 > 代码库 > hdu--3911--线段树<我最近爱上她了>
hdu--3911--线段树<我最近爱上她了>
突然间 觉得 线段树是个很优美的数据结构~~ 太灵活了 通过几个var 可以完成太多功能
这题其实我也想说 好累啊 写的...但似乎 因为它是线段树的缘故就显得很平常了...
这里主要考察了lazy标记---延迟父节点对子节点的更新
这边还算简单的 只需要1个Lazy标记 麻烦的是需要2个 甚至3个的...
这边至于 黑白关系 就是一个 异或运算 可以搞定
要注意下 询问一段区间内 最长的连续的1的个数 必须分成3段来考虑 通过是否包含中点 来划分 左 右 中
虽然 这边是问最长的连续的1的个数 但我有必要记录下最长的连续0的个数 因为这样进行一个Update后 答案就是变成了刚才的最长的连续0的个数
这边我们分别需要考虑一个区间从左边与右边分别来看的 含连续0或1的最长区间 再统一考虑得出一个区间内最长连续0或1的长度
真的 线段树 需要思考的范围很多
这边的话 我分别试了下 2种不同的对于区间进行操作的方式 发现时间上第一种 更加快点
1 /* 2 线段树所有节点理论空间值是2n-1，但是实际上所占空间会超过这个数。因为一颗线段树的高度是log(n - 1) + 1， 3 而线段树是完全二叉树，所以要开够最后一层，所以总的空间就是1+2^1 + ... + 2^(log(n - 1) + 1) = 4(n - 1) - 1。 4 所以保守要开4倍空间，但是大多数情况下3倍空间也是能过的。 5 */ 6 #include <iostream> 7 #include <algorithm> 8 using namespace std; 9 10 const int size = 100010; 11 struct data // 1是黑色 0是白色 12 { 13 int L; 14 int R; 15 int len; 16 int Lone , Rone , Lzero , Rzero , maxOne , maxZero; 17 int color; 18 }tree[size*4]; 19 20 void solve( int root ) 21 { 22 swap( tree[root].Lone , tree[root].Lzero ); 23 swap( tree[root].Rone , tree[root].Rzero ); 24 swap( tree[root].maxOne , tree[root].maxZero ); 25 tree[root].color ^= 1; 26 } 27 28 void pushUp( int root ) 29 { 30 tree[root].Lone = tree[root<<1].Lone; 31 if( tree[root<<1].Lone == tree[root<<1].len ) 32 tree[root].Lone += tree[root<<1|1].Lone; 33 34 tree[root].Lzero = tree[root<<1].Lzero; 35 if( tree[root<<1].Lzero == tree[root<<1].len ) 36 tree[root].Lzero += tree[root<<1|1].Lzero; 37 38 tree[root].Rone = tree[root<<1|1].Rone; 39 if( tree[root<<1|1].Rone == tree[root<<1|1].len ) 40 tree[root].Rone += tree[root<<1].Rone; 41 42 tree[root].Rzero = tree[root<<1|1].Rzero; 43 if( tree[root<<1|1].Rzero == tree[root<<1|1].len ) 44 tree[root].Rzero += tree[root<<1].Rzero; 45 46 tree[root].maxOne = max( max( tree[root<<1].maxOne , tree[root<<1|1].maxOne ) , tree[root<<1].Rone + tree[root<<1|1].Lone ); 47 tree[root].maxZero = max( max( tree[root<<1].maxZero , tree[root<<1|1].maxZero) , tree[root<<1].Rzero + tree[root<<1|1].Lzero ); 48 } 49 50 void pushDown( int root ) 51 { 52 solve( root<<1 ); 53 solve( root<<1|1 ); 54 tree[root].color = 0; 55 } 56 57 void build( int root , int L , int R ) 58 { 59 int Mid = ( L + R ) >> 1 , num; 60 tree[root].L = L; 61 tree[root].R = R; 62 tree[root].len = R - L + 1; 63 tree[root].color = 0; 64 if( L==R ) 65 { 66 cin >> num; 67 if( num == 1 ) 68 { 69 tree[root].Lone = tree[root].Rone = tree[root].maxOne = 1; 70 tree[root].Lzero = tree[root].Rzero = tree[root].maxZero = 0; 71 } 72 else 73 { 74 tree[root].Lone = tree[root].Rone = tree[root].maxOne = 0; 75 tree[root].Lzero = tree[root].Rzero = tree[root].maxZero = 1; 76 } 77 return; 78 } 79 build( root<<1 , L , Mid ); 80 build( root<<1|1 , Mid+1 , R ); 81 pushUp( root ); 82 } 83 84 void update( int root , int L , int R ) 85 { 86 int Mid = ( tree[root].L + tree[root].R ) >> 1; 87 if( tree[root].L == L && tree[root].R == R ) 88 { 89 solve( root ); 90 return; 91 } 92 if( tree[root].color ) 93 pushDown( root ); 94 if( R <= Mid ) 95 update( root<<1 , L , R ); 96 else if( L >= Mid+1 ) 97 update( root<<1|1 , L , R ); 98 else 99 {100 update( root<<1 , L , Mid );101 update( root<<1|1 , Mid+1 , R );102 }103 pushUp( root );104 }105 106 int query( int root , int L , int R )107 {108 int a = 0 , b = 0 , var = 0;109 int Mid = ( tree[root].L + tree[root].R ) >> 1;110 if( tree[root].L == L && tree[root].R == R )111 {112 return tree[root].maxOne;113 }114 if( tree[root].color )115 pushDown( root );116 if( R <= Mid )117 return query( root<<1 , L , R );118 else if( L >= Mid+1 )119 return query( root<<1|1 , L , R );120 else121 {122 a = query( root<<1 , L , Mid );123 b = query( root<<1|1 , Mid+1 , R );124 var = min( Mid - L + 1 , tree[root<<1].Rone ) + min( R - Mid , tree[root<<1|1].Lone );125 return max( max(a,b) , var );126 }127 }128 129 int main()130 {131 cin.sync_with_stdio(false);132 int n , m , x , y , op;133 while( cin >> n )134 {135 build( 1 , 1 , n );136 cin >> m;137 while( m-- )138 {139 cin >> op >> x >> y;140 if( op == 1 )141 {142 update( 1 , x , y );143 }144 else145 {146 cout << query( 1 , x , y ) << endl;147 }148 }149 }150 return 0;151 }
1 /* 2 线段树所有节点理论空间值是2n-1，但是实际上所占空间会超过这个数。因为一颗线段树的高度是log(n - 1) + 1， 3 而线段树是完全二叉树，所以要开够最后一层，所以总的空间就是1+2^1 + ... + 2^(log(n - 1) + 1) = 4(n - 1) - 1。 4 所以保守要开4倍空间，但是大多数情况下3倍空间也是能过的。 5 */ 6 #include <iostream> 7 #include <algorithm> 8 using namespace std; 9 10 const int size = 100010; 11 struct data // 1是黑色 0是白色 12 { 13 int L; 14 int R; 15 int len; 16 int Lone , Rone , Lzero , Rzero , maxOne , maxZero; 17 int color; 18 }tree[size*4]; 19 20 void solve( int root ) 21 { 22 swap( tree[root].Lone , tree[root].Lzero ); 23 swap( tree[root].Rone , tree[root].Rzero ); 24 swap( tree[root].maxOne , tree[root].maxZero ); 25 tree[root].color ^= 1; 26 } 27 28 void pushUp( int root ) 29 { 30 tree[root].Lone = tree[root<<1].Lone; 31 if( tree[root<<1].Lone == tree[root<<1].len ) 32 tree[root].Lone += tree[root<<1|1].Lone; 33 34 tree[root].Lzero = tree[root<<1].Lzero; 35 if( tree[root<<1].Lzero == tree[root<<1].len ) 36 tree[root].Lzero += tree[root<<1|1].Lzero; 37 38 tree[root].Rone = tree[root<<1|1].Rone; 39 if( tree[root<<1|1].Rone == tree[root<<1|1].len ) 40 tree[root].Rone += tree[root<<1].Rone; 41 42 tree[root].Rzero = tree[root<<1|1].Rzero; 43 if( tree[root<<1|1].Rzero == tree[root<<1|1].len ) 44 tree[root].Rzero += tree[root<<1].Rzero; 45 46 tree[root].maxOne = max( max( tree[root<<1].maxOne , tree[root<<1|1].maxOne ) , tree[root<<1].Rone + tree[root<<1|1].Lone ); 47 tree[root].maxZero = max( max( tree[root<<1].maxZero , tree[root<<1|1].maxZero) , tree[root<<1].Rzero + tree[root<<1|1].Lzero ); 48 } 49 50 void pushDown( int root ) 51 { 52 solve( root<<1 ); 53 solve( root<<1|1 ); 54 tree[root].color = 0; 55 } 56 57 void build( int root , int L , int R ) 58 { 59 int Mid = ( L + R ) >> 1 , num; 60 tree[root].L = L; 61 tree[root].R = R; 62 tree[root].len = R - L + 1; 63 tree[root].color = 0; 64 if( L==R ) 65 { 66 cin >> num; 67 if( num == 1 ) 68 { 69 tree[root].Lone = tree[root].Rone = tree[root].maxOne = 1; 70 tree[root].Lzero = tree[root].Rzero = tree[root].maxZero = 0; 71 } 72 else 73 { 74 tree[root].Lone = tree[root].Rone = tree[root].maxOne = 0; 75 tree[root].Lzero = tree[root].Rzero = tree[root].maxZero = 1; 76 } 77 return; 78 } 79 build( root<<1 , L , Mid ); 80 build( root<<1|1 , Mid+1 , R ); 81 pushUp( root ); 82 } 83 84 void update( int root , int L , int R ) 85 { 86 int Mid = ( tree[root].L + tree[root].R ) >> 1; 87 if( tree[root].L >= L && tree[root].R <= R ) 88 { 89 solve( root ); 90 return; 91 } 92 if( tree[root].color ) 93 pushDown( root ); 94 if( L <= Mid ) 95 update( root<<1 , L , R ); 96 if( R >= Mid+1 ) 97 update( root<<1|1 , L , R ); 98 pushUp( root ); 99 }100 101 int query( int root , int L , int R )102 {103 int a = 0 , b = 0 , var = 0;104 int Mid = ( tree[root].L + tree[root].R ) >> 1;105 if( tree[root].L >= L && tree[root].R <= R )106 {107 return tree[root].maxOne;108 }109 if( tree[root].color )110 pushDown( root );111 if( L <= Mid )112 a = query( root<<1 , L , R );113 if( R >= Mid+1 )114 b = query( root<<1|1 , L , R );115 var = min( Mid - L + 1 , tree[root<<1].Rone ) + min( R - Mid , tree[root<<1|1].Lone );116 return max( max(a,b) , var );117 }118 119 int main()120 {121 cin.sync_with_stdio(false);122 int n , m , x , y , op;123 while( cin >> n )124 {125 build( 1 , 1 , n );126 cin >> m;127 while( m-- )128 {129 cin >> op >> x >> y;130 if( op == 1 )131 {132 update( 1 , x , y );133 }134 else135 {136 cout << query( 1 , x , y ) << endl;137 }138 }139 }140 return 0;141 }
我应该还会继续做几题 来找感觉 蛮有意思的 =_=
today:
努力想得到什么东西，其实只要沉着镇静、实事求是，就可以轻易地、神不知鬼不觉地达到目的。
而如果过于使劲，闹得太凶，太幼稚，太没有经验，就哭啊，抓啊，拉啊，像一个小孩扯桌布，
结果却是一无所获，只不过把桌上的好东西都扯到地上，永远也得不到了。
hdu--3911--线段树<我最近爱上她了>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。