首页 > 代码库 > 线段树 区间合并

线段树 区间合并

2024-07-17 23:38:56   228人阅读

poj3667 Hotel

区间合并入门题，照着代码打的，

题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边
       2 a b:将[a,a+b-1]的房间清空
思路:记录区间中最长的空房间，开三个数组，msum[rt]表示节点rt内连续的1的个数的最大值，lsum[rt]表示从节点rt左端点开始连续1的个数，rsum[rt]表示从节点rt右端点开始连续1的个数。。
线段树操作:update:区间替换 query:询问满足条件的最左端点

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<string> 6 #include<cmath> 7 #include<map> 8 #include<queue> 9 10 using namespace std;11 12 #define mnx 5000513 #define Pi acos(-1.0)14 #define ull unsigned long long15 #define ll long long 16 #define inf 0x3f3f3f3f17 #define eps 1e-818 #define MP make_pair19 #define lson l, m, rt << 120 #define rson m+1, r, rt << 1 | 121 #define mod 233333322 23 int msum[mnx<<2], lsum[mnx<<2], rsum[mnx<<2], cover[mnx<<2];24 void pushup( int rt, int m ){25     lsum[rt] = lsum[rt<<1];26     rsum[rt] = rsum[rt<<1|1];27     if( lsum[rt] == m - ( m >> 1 ) ) lsum[rt] += lsum[rt<<1|1];28     if( rsum[rt] == ( m >> 1 ) ) rsum[rt] += rsum[rt<<1];29     msum[rt] = max( lsum[rt<<1|1] + rsum[rt<<1], max( msum[rt<<1], msum[rt<<1|1] ) );30 }31 void pushdown( int rt, int m ){32     if( cover[rt] != -1 ){33         cover[rt<<1] = cover[rt<<1|1] = cover[rt];34         msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : m - ( m >> 1 );35         msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : m >> 1;36         cover[rt] = -1;37     }38 }39 void build( int l, int r, int rt ){40     msum[rt] = lsum[rt] = rsum[rt] = r - l + 1;41     if( l == r ) return;42     int m = ( l + r ) >> 1;43     build( lson ); build( rson );44 }45 void update( int L, int R, int v, int l, int r, int rt ){46     if( L <= l && R >= r ){47         msum[rt] = rsum[rt] = lsum[rt] = v ? 0 : r - l + 1;48         cover[rt] = v;49         return ;50     }51     pushdown( rt, r - l + 1 );52     int m = ( l + r ) >> 1;53     if( L <= m ) update( L, R, v, lson );54     if( R > m ) update( L, R, v, rson );55     pushup( rt, r - l + 1 );56 }57 int query( int v, int l, int r, int rt ){58     if( l == r ) return l;59     pushdown( rt, r - l + 1 );60     int m = ( l + r ) >> 1;61     if( msum[rt<<1] >= v ) return query( v, lson );62     else if( rsum[rt<<1] + lsum[rt<<1|1] >= v ) return m - rsum[rt<<1] + 1;63     else return query( v, rson );64 }65 int main(){66     int n, m;67     while( scanf( "%d %d", &n, &m ) != EOF ){68         memset( cover, -1, sizeof(cover) );69         build( 1, n, 1 );70         int op, a, b;71         while( m-- ){72             scanf( "%d", &op );73             if( op == 1 ){74                 scanf( "%d", &a );75                 if( msum[1] < a ){76                     puts( "0" ); continue;77                 }78                 int ans = query( a, 1, n, 1 );79                 printf( "%d\n", ans );80                 update( ans, ans + a - 1, 1, 1, n, 1 );81             }82             else{83                 scanf( "%d %d", &a, &b );84                 update( a, a + b - 1, 0, 1, n, 1 );85             }86         }87     }88     return 0;89 }
View Code

 


联系
我们