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 }

View Code

明天是個特殊的日子。。

轉載于:https://www.cnblogs.com/radical/p/4162103.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/376408.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/376408.shtml
英文地址，請注明出處：http://en.pswp.cn/news/376408.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！