首页 > 代码库 > hdu--5091--线段树

hdu--5091--线段树

自己还是没有做出来= =  

我去用段树 而不是点树去做了

而貌似段树不行啊。

我还没想明白 ccc

  1 #include <iostream>  2 #include <algorithm>  3 using namespace std;  4   5 int cnt;  6 const int size = 20010;  7 struct data  8 {  9     int L , R , flag , sum; 10     int x1 , x2 , y; 11     data(){}; 12     data( int u , int w , int v , int p ):x1(u),x2(w),y(v),flag(p){}; 13 }tree[size<<2],mat[size]; 14 int seg[size]; 15  16 bool cmp( const data p , const data q ) 17 { 18     if( p.y==q.y ) 19         return p.flag > q.flag; 20     return p.y < q.y; 21 } 22  23 void pushDown( int rt ) 24 { 25     if( tree[rt].flag ) 26     { 27         tree[rt<<1].flag += tree[rt].flag; 28         tree[rt<<1|1].flag += tree[rt].flag; 29         tree[rt<<1].sum += tree[rt].flag; 30         tree[rt<<1|1].sum += tree[rt].flag; 31         tree[rt].flag = 0; 32     } 33 } 34  35 void pushUp( int rt ) 36 { 37     tree[rt].sum = max( tree[rt<<1].sum , tree[rt<<1|1].sum ); 38 } 39  40 void build( int rt , int L , int R ) 41 { 42     int M = ( L + R ) >> 1; 43     tree[rt].L = L , tree[rt].R = R; 44     tree[rt].flag = tree[rt].sum = 0; 45     if( L == R ) 46         return ; 47     build( rt<<1 , L , M ); 48     build( rt<<1|1 , M+1 , R ); 49 } 50  51 void update( int rt , int L , int R , int var ) 52 { 53     int M = ( tree[rt].L + tree[rt].R ) >> 1; 54     if( tree[rt].L == L && tree[rt].R == R ) 55     {     56         tree[rt].flag += var; 57         tree[rt].sum += var; 58         return ; 59     } 60     pushDown( rt ); 61     if( R<=M ) 62         update( rt<<1 , L , R , var ); 63     else if( L>=M+1 ) 64         update( rt<<1|1 , L , R , var ); 65     else 66     { 67         update( rt<<1 , L , M , var ); 68         update( rt<<1|1 , M+1 , R , var ); 69     } 70     pushUp( rt ); 71 } 72  73 int main() 74 { 75     cin.sync_with_stdio(false); 76     int n , w , h , x , y , L , R , ans; 77     while( cin >> n >> w >> h ) 78     { 79         if( n<0 ) 80             break; 81         cnt = 1; 82         for( int i = 0 ; i<n ; i++ ) 83         { 84             cin >> x >> y; 85             seg[cnt] = x; 86             mat[cnt++] = data( x , x+w , y , 1 ); 87             seg[cnt] = x+w; 88             mat[cnt++] = data( x , x+w , y+h , -1 ); 89         } 90         sort( seg+1 , seg+cnt ); 91         sort( mat+1 , mat+cnt , cmp ); 92         cnt = unique( seg+1 , seg+cnt ) - seg; 93         build( 1 , 1 , cnt-1 ); 94         ans = 0; 95         for( int i = 1 ; i<=(n<<1) ; i++ ) 96         { 97             L = lower_bound( seg+1 , seg+cnt , mat[i].x1 ) - seg; 98             R = lower_bound( seg+1 , seg+cnt , mat[i].x2 ) - seg; 99             update( 1 , L , R , mat[i].flag );100             ans = max( ans , tree[1].sum );101         }102         cout << ans << endl;103     }104     return 0;105 }
View Code

 

hdu--5091--线段树