首页 > 代码库 > hdu--4027--不错的线段树

hdu--4027--不错的线段树

这题 蛮好的 如果用心去感受<讲得好像太文艺了>

不知道 你们有没有想过为什么 有时候进行区间更新操作的时候 可以直接对整个区间进行操作 而不必要一个点 一个点地去更新

因为 我们对这个区间内的每个数 都是相同的操作 所以可以放在一起操作 就像一起+- K什么的

但这里呢 是对[ L , R ]这个区间内的每一个元素 开平方  我们只能一个点 一个点地更新.

那你可能会想 这样我们就发挥不了线段树的优势了啊 和for遍历一样了

我们还是可以运用下 标记  虽然不是延迟更新的思想 但效果上也能节省很多时间

我们知道<1,3>无限开平方 下去 永远都是1  所以这是没必要的  我们就应该标记出这些特殊数据

orz...11.11 分手半年多了 我要摆脱单身了吗?

  1 #include <iostream>  2 #include <cmath>  3 #include <algorithm>  4 using namespace std;  5   6 typedef long long LL;  7 const int size = 100010;  8 struct data  9 { 10     int L; 11     int R; 12     bool flag;//判断是否为1 13     LL sum; 14 }tree[size*4]; 15  16 void pushUp( int root ) 17 { 18     tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum; 19     tree[root].flag = tree[root<<1].flag && tree[root<<1|1].flag; 20 } 21  22 void build( int root , int L , int R ) 23 { 24     int Mid = ( L + R ) >> 1; 25     tree[root].L = L; 26     tree[root].R = R; 27     tree[root].flag = false; 28     if( L == R ) 29     { 30         cin >> tree[root].sum; 31         if( tree[root].sum<=1 ) 32             tree[root].flag = true; 33         return ; 34     } 35     build( root<<1 , L , Mid ); 36     build( root<<1|1 , Mid+1 , R ); 37     pushUp( root ); 38 } 39  40 void update( int root , int L , int R ) 41 { 42     int Mid = ( tree[root].L + tree[root].R ) >> 1; 43     if( tree[root].flag ) 44         return; 45     if( tree[root].L  == L && tree[root].R == R && L == R ) 46     { 47         tree[root].sum = (LL)sqrt( tree[root].sum*1.0 ); 48         if( tree[root].sum <= 1 ) 49         { 50             tree[root].flag = true; 51         } 52         return ; 53     } 54     if( R<=Mid ) 55         update( root<<1 , L , R ); 56     else if( L>=Mid+1 ) 57         update( root<<1|1 , L , R ); 58     else 59     { 60         update( root<<1 , L , Mid ); 61         update( root<<1|1 , Mid+1 , R ); 62     } 63     pushUp( root ); 64 } 65  66 LL query( int root , int L , int R ) 67 { 68     int Mid = ( tree[root].L + tree[root].R ) >> 1; 69     LL ans = 0; 70     if( tree[root].L == L && tree[root].R == R ) 71     { 72         return tree[root].sum ; 73     } 74     if( R<=Mid ) 75         ans += query( root<<1 , L , R ); 76     else if( L>=Mid+1 ) 77         ans += query( root<<1|1 , L , R ); 78     else 79     { 80         ans += query( root<<1 , L , Mid ); 81         ans += query( root<<1|1 , Mid+1 , R ); 82     } 83     return ans; 84 } 85  86 int main() 87 { 88     cin.sync_with_stdio(false); 89     int n , m , op , x , y; 90     int cnt = 1; 91     while( cin >> n ) 92     { 93         build( 1 , 1 , n ); 94         cin >> m; 95         cout << "Case #" << cnt++ << ":" << endl; 96         while( m-- ) 97         { 98             cin >> op >> x >> y; 99             if( x>y )100                 swap( x , y );101             if( !op )102             {103                 update( 1 , x , y );104             }105             else106             {107                 cout << query( 1 , x , y ) << endl;108             }109         }110         cout << endl;111     }112     return 0;113 }
View Code

 

 

today:

  科比 布莱恩特

  无需多言

  老大

 

hdu--4027--不错的线段树