首页 > 代码库 > hdu--4902--线段树
hdu--4902--线段树
题意 前面一段废话= =
这题 最有意思的应该是出题人 是clj
这题的时限放的太宽了 给了15s 我也是醉了
区间更新。
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int size = 200010; 6 int a[size]; 7 struct data 8 { 9 int L , R , maxVar; 10 bool flag; 11 }tree[size<<2]; 12 13 int gcd( int x , int y ) 14 { 15 return x % y == 0 ? y : gcd( y , x%y ); 16 } 17 18 void pushDown( int rt ) 19 { 20 tree[rt<<1].maxVar = tree[rt<<1|1].maxVar = tree[rt].maxVar; 21 tree[rt<<1].flag = tree[rt<<1|1].flag = true; 22 tree[rt].flag = false; 23 } 24 25 void pushUp( int rt ) 26 { 27 tree[rt].maxVar = max( tree[rt<<1].maxVar , tree[rt<<1|1].maxVar ); 28 } 29 30 void build( int rt , int L , int R ) 31 { 32 int M = ( L + R ) >> 1; 33 tree[rt].L = L , tree[rt].R = R; 34 tree[rt].flag = false; 35 if( L==R ) 36 { 37 tree[rt].maxVar = a[L]; 38 tree[rt].flag = true; 39 return ; 40 } 41 build( rt<<1 , L , M ); 42 build( rt<<1|1 , M+1 , R ); 43 pushUp( rt ); 44 } 45 46 void update( int rt , int L , int R , int x , int op ) 47 { 48 int M = ( tree[rt].L + tree[rt].R ) >> 1; 49 if( tree[rt].L == L && tree[rt].R == R ) 50 { 51 if( op==1 ) 52 { 53 tree[rt].maxVar = x; 54 tree[rt].flag = true; 55 return; 56 } 57 else 58 { 59 if( tree[rt].maxVar<=x ) 60 return ; 61 if( tree[rt].flag && tree[rt].maxVar>x ) 62 { 63 tree[rt].maxVar = gcd( tree[rt].maxVar , x ); 64 return; 65 } 66 } 67 } 68 if( tree[rt].flag ) 69 { 70 pushDown( rt ); 71 } 72 if( R<=M ) 73 { 74 update( rt<<1 , L , R , x , op ); 75 } 76 else if( L>=M+1 ) 77 { 78 update( rt<<1|1 , L , R , x , op ); 79 } 80 else 81 { 82 update( rt<<1 , L , M , x , op ); 83 update( rt<<1|1 , M+1 , R , x , op ); 84 } 85 pushUp( rt ); 86 } 87 88 void solve( int rt , int L , int R ) 89 { 90 int M = ( tree[rt].L + tree[rt].R ) >> 1; 91 if( L == R ) 92 { 93 cout << tree[rt].maxVar << " "; 94 return ; 95 } 96 if( tree[rt].flag ) 97 { 98 pushDown( rt ); 99 }100 solve( rt<<1 , L , M );101 solve( rt<<1|1 , M+1 , R );102 }103 104 int main()105 {106 cin.sync_with_stdio(false);107 int t , n , m , op , L , R , x;108 cin >> t;109 while( t-- )110 {111 cin >> n;112 for( int i = 1 ; i<=n ; i++ )113 cin >> a[i];114 build( 1 , 1 , n );115 cin >> m;116 while( m-- )117 {118 cin >> op >> L >> R >> x;119 update( 1 , L , R , x , op );120 }121 solve( 1 , 1 , n );122 cout << endl;123 }124 return 0;125 }
明天 是个特殊的日子 。。
hdu--4902--线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。