[PKU/POJ][3667][Hotel][线段树]

题目意思大概就是有一连串的房子。客人来时会要求订其中连续的 k 个房子，要你给出连续 k 个房子的最小编号。同时也会退订房间的操作。

用线段树来维护房子的订阅情况。线段树记录 4 个域。

struct Node{
	int Lx;     //  区间从左端点起连续的最大长度 
	int Rx;     //  区间以右端点结束的最大连续长度 
	int Ax;     //  区间全局最大连续长度 
	int cover;  //  标记区间是否被覆盖 0， 1， -1 
};

cover 为 0 表示这个区间里的房子都没订，为 1 表示这个区间房子都订了， 为 -1 表示其它情况。

Lx,  Rx 是为了更新 Ax。。

 

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int const N= 50010;
int n, m;
int COLOR;

struct Node{
	int Lx;     //  区间从左端点起连续的最大长度 
	int Rx;     //  区间以右端点结束的最大连续长度 
	int Ax;     //  区间全局最大连续长度 
	int cover;  //  标记区间是否被覆盖 0， 1， -1 
}

tb[N<<2];

void build( int L, int R, int rt ){
	if( L== R ){
		tb[rt].Lx= 1; tb[rt].Rx= 1; tb[rt].Ax= 1;
		return;
	}
	
	int mid= (L+ R)>>1;
	build( L, mid, rt<<1 );
	build( mid+ 1, R, rt<<1|1 );
	
	tb[rt].Lx= tb[rt].Rx= tb[rt].Ax= R- L+ 1;
	tb[rt].cover= 0;
}

int query( int x, int L, int R, int rt ){
	if( tb[rt].Ax== x && R- L+ 1== x ) return L;
	
	if( tb[rt].Ax>= x ){
		int mid= (L+ R)>>1;
		
		if( tb[rt].cover!= -1 ){
			tb[rt<<1].cover= tb[rt<<1|1].cover= tb[rt].cover;
			
			if( tb[rt].cover== 0 ){
				tb[rt<<1].Ax= tb[rt<<1].Lx= tb[rt<<1].Rx= mid- L+ 1;
				tb[rt<<1|1].Ax= tb[rt<<1|1].Lx= tb[rt<<1|1].Rx= R- mid;
			}
			else{
				tb[rt<<1].Ax= tb[rt<<1].Lx= tb[rt<<1].Rx= 0;
				tb[rt<<1|1].Ax= tb[rt<<1|1].Lx= tb[rt<<1|1].Rx= 0;
			}
			tb[rt].cover= -1;
		}
		
		if( tb[rt<<1].Ax>= x ) return query( x, L, mid, rt<<1 );
		else if( min( mid- L+ 1, tb[rt<<1].Rx )+ min( R- mid, tb[rt<<1|1].Lx )>= x ){
			return mid- min(  mid- L+ 1, tb[rt<<1].Rx )+ 1;
		}
		else if( tb[rt<<1|1].Ax>= x ) return query( x, mid+ 1, R, rt<<1| 1 );
	}
	
	return 0;
}

void update( int x, int y, int L, int R, int rt ){
	if( L== x && R== y ){
		tb[rt].cover= COLOR;
		if( COLOR== 0 ) tb[rt].Ax= tb[rt].Lx= tb[rt].Rx= R- L+ 1;
		else tb[rt].Ax= tb[rt].Lx= tb[rt].Rx= 0;
		return;
	}
	
	int mid= (L+ R)>>1;
	if( tb[rt].cover!= -1 ){
		tb[rt<<1].cover= tb[rt<<1|1].cover= tb[rt].cover;
		
		if( tb[rt].cover== 0 ){
			tb[rt<<1].Ax= tb[rt<<1].Lx= tb[rt<<1].Rx= mid- L+ 1;
			tb[rt<<1|1].Ax= tb[rt<<1|1].Lx= tb[rt<<1|1].Rx= R- mid;
		}
		else{
			tb[rt<<1].Ax= tb[rt<<1].Lx= tb[rt<<1].Rx= 0;
			tb[rt<<1|1].Ax= tb[rt<<1|1].Lx= tb[rt<<1|1].Rx= 0;
		}
		tb[rt].cover= -1;
	}
	
	if( y<= mid ) update( x, y, L, mid, rt<<1 );
	else if( x> mid ) update( x, y, mid+ 1, R, rt<<1|1 );
	else{
		update( x, mid, L, mid, rt<<1 );
		update( mid+ 1, y,  mid+ 1, R, rt<<1|1 );
	}
	
	tb[rt].Ax= max( tb[rt<<1].Ax, tb[rt<<1|1].Ax );
	if( tb[rt<<1].Lx== mid- L+ 1 ) tb[rt].Lx= tb[rt<<1].Lx+ tb[rt<<1|1].Lx;
	else tb[rt].Lx= tb[rt<<1].Lx;
	
	if( tb[rt<<1|1].Rx== R- mid ) tb[rt].Rx= tb[rt<<1|1].Rx+ tb[rt<<1].Rx;
	else tb[rt].Rx= tb[rt<<1|1].Rx;
	
	tb[rt].Ax= max( tb[rt].Ax, max( tb[rt].Lx, tb[rt].Rx ) );
	tb[rt].Ax= max( tb[rt].Ax, tb[rt<<1].Rx+ tb[rt<<1|1].Lx );
}

int main(){
	scanf("%d%d",&n,&m );
	
	build( 1, n, 1 );
	for( int i= 0; i< m; ++i ){
		int x, y, z;
		scanf("%d",&x);
		
		if( x== 1 ){
			scanf("%d",&y );
			
			int pos= query( y, 1, n, 1 );
			printf("%d\n", pos );
			
			if( pos!= 0 ){
				COLOR= 1;
				update( pos, pos+ y- 1, 1, n, 1 );
			}
		}
		else{
			scanf("%d%d",&y,&z );
			
			COLOR= 0;
			update( y, y+ z- 1, 1, n, 1 );
		}
	}
	
	return 0;
}