POJ1823Hotel

The "Informatics" hotel is one of the most luxurious hotels from Galaciuc. A lot of tourists arrive or leave this hotel in one year. So it is pretty difficult to keep the evidence of the occupied rooms. But this year the owner of the hotel decided to do some changes. That's why he engaged you to write an efficient program that should respond to all his needs.
Write a program that should efficiently respond to these 3 types of instructions: type 1: the arrival of a new group of tourists A group of M tourists wants to occupy M free consecutive rooms. The program will receive the number i which represents the start room of the sequence of the rooms that the group wants to occupy and the number M representing the number of members of the group. It is guaranteed that all the rooms i,i+1,..,i+M-1 are free at that moment. type 2: the departure of a group of tourists The tourists leave in groups (not necessarilly those groups in which they came). A group with M members leaves M occupied and consecutive rooms. The program will receive the number i representing the start room of the sequence of the released rooms and the number M representing the number of members of the group. It is guaranteed that all the rooms i,i+1,..,i+M-1 are occupied.
type 3: the owner's question The owner of the hotel may ask from time to time which is the maximal length of a sequence of free consecutive rooms. He needs this number to know which is the maximal number of tourists that could arrive to the hotel. You can assume that each room may be occupied by no more than one tourist.

On the first line of input, there will be the numbers N (3 <= N <= 16 000) representing the number of the rooms and P (3 <= P <= 200 000) representing the number of the instructions.
The next P lines will contain the number c representing the type of the instruction:

if c is 1 then it will be followed (on the same line) by 2 other numbers, i and M, representing the number of the first room distributed to the group and the number of the members
if c is 2 then it will be followed (on the same line) by 2 other numbers, i and M, representing the number of the first room that will be released and the number of the members of the group that is leaving
if c is 3 then it will not be followed by any number on that line, but the program should output in the output file the maximal length of a sequence of free and consecutive rooms

In the output you will print for each instruction of type 3, on separated lines, the maximal length of a sequence of free and consecutive rooms. Before the first instruction all the rooms are free.

Romania OI 2002

#include"iostream"

#include"stdio.h"

#include"cmath"

using namespace std;

const int MAX=16000;

struct Node{

int right,left;

int max,lmax,rmax;

int status;//节点状态：0表示该段全空，1表示该段部分被占用，2表示该段全部被占用

};

Node node[4*MAX];

void build(int left,int right,int i){

//cout<<"left: "<<left<<" right: "<<right<<endl;

node[i].left=left;

node[i].right=right;

node[i].max=node[i].lmax=node[i].rmax=right-left+1;

// cout<<"i: "<<i<<" "<<"node.max: "<<node[i].max<<endl;

node[i].status=0;

if(left==right)

return;

else{

int mid=(left+right)/2;

build(left,mid,2*i+1);

build(mid+1,right,2*i+2);//注意到题意要求叶节点的区段是自由一个数的

}

void modify(int left,int right,int i,int targetOfStatus){//画图帮助理解！！！

//判断递归终止条件：

if(left==node[i].left&&right==node[i].right){

if(targetOfStatus==0){

node[i].max=node[i].lmax=node[i].rmax=node[i].right-node[i].left+1;

node[i].status=0;

}

else if(targetOfStatus==2){

node[i].max=node[i].lmax=node[i].rmax=0;

node[i].status=2;

}

return;

}

//根据之前插入或者删除操作进行更新操作：

//当前节点完全递归返回前未被占用，保证“当前节点的子节点的状态被标记为0”优先级最高

//具体解析：因为之前操作中的插入或者删除操作都是到达满足if(tree[i].left==x&&tree[i].right==y)的条件之后就返回了，

//但是我们之后要进行的插入和删除操作要是区段有可能比之前涉及到的区段小，这个时候在递归之前判断当前节点状态并且

//对相应左子树和右子树执行更新操作就很有必要了

if(node[i].status==0){

node[2*i+1].status=0;

node[2*i+1].max=node[2*i+1].lmax=node[2*i+1].rmax=node[2*i+1].right-node[2*i+1].left+1;

node[2*i+2].status=0;

node[2*i+2].max=node[2*i+2].lmax=node[2*i+2].rmax=node[2*i+2].right-node[2*i+2].left+1;

}

else if(node[i].status==2){

node[2*i+1].status=2;

node[2*i+1].max=node[2*i+1].lmax=node[2*i+1].rmax=0;

node[2*i+2].status=2;

node[2*i+2].max=node[2*i+2].lmax=node[2*i+2].rmax=0;

}

//递归操作：（可以以将(1,1)插入节点(1,2)中作为范例进行理解）

int mid=(node[i].left+node[i].right)>>1;

if(right<=mid)

modify(left,right,2*i+1,targetOfStatus);

else if(left>mid)//考虑到计算机整除‘>>2’的特性

modify(left,right,2*i+2,targetOfStatus);

else{

modify(left,mid,2*i+1,targetOfStatus);

modify(mid+1,right,2*i+2,targetOfStatus);

}

// cout<<"i: "<<i<<" "<<"node[i].left: "<<node[i].left<<" "<<"left: "<<left

// <<" "<<"node[i].right: "<<node[i].right<<"right: "<<right<<endl;

//延迟处理：

if(node[2*i+1].status==0&&node[2*i+2].status==0){//左右子树均全空

node[i].status=0;

//由上面注释打表得之：此处必须用node[i].right-node[i].left+1而不是right-left+1（其他情况可类推）

//原因：node是线段树的节点而[left,right]只是待插入线段而已！

node[i].max=node[i].lmax=node[i].rmax=node[i].right-node[i].left+1;

}

else if(node[2*i+1].status==0&&node[2*i+2].status==2){//左子树全空，右子树全被占用

node[i].status=1;

node[i].max=node[i].lmax=node[2*i+1].max;

node[i].rmax=0;

}

else if(node[2*i+1].status==2&&node[2*i+2].status==0){//左子树被占用，右子树全空

node[i].status=1;

node[i].lmax=0;

node[i].max=node[i].rmax=node[2*i+2].max;

}

else if(node[2*i+1].status==2&&node[2*i+2].status==2){//左右子树都全被占用

node[i].status=2;

node[i].max=node[i].lmax=node[i].rmax=0;

}

else{//左子树或者右子树含有部分被占用的情况（至少有一个子树是1，包含(1,0)(1,2)(0,1)(2,1)(1,1)五种情况）

node[i].status=1;

node[i].max=max(node[2*i+1].max,node[2*i+2].max);

node[i].max=max(node[i].max,node[2*i+1].rmax+node[2*i+2].lmax);

//处理node[i].lmax

if(node[2*i+1].status==0)

node[i].lmax=node[2*i+1].max+node[2*i+2].lmax;

else

node[i].lmax=node[2*i+1].lmax;

//处理node[i].rmax

if(node[2*i+2].status==0)

node[i].rmax=node[2*i+1].rmax+node[2*i+2].max;

else

node[i].rmax=node[2*i+2].rmax;

}

int main(){

int Nroom,Ninstruct;

scanf("%d%d",&Nroom,&Ninstruct);//必须用scanf否则会TLE！

int type,begin,number;

build(0,Nroom-1,0);

while(Ninstruct--){

scanf("%d",&type);

if(type==1){

scanf("%d%d",&begin,&number);

modify(begin-1,begin-1+number-1,0,2);//node的index从0开始

}

else if(type==2){

scanf("%d%d",&begin,&number);

modify(begin-1,begin-1+number-1,0,0);//node的index从0开始

}

else if(type==3){

printf("%d\n",node[0].max);

/*

cout<<"node.left,node.right,node.status,node.max,node.lmax,node.rmax: \n";

for(int i=0;i<29;i++){

cout<<node[i].left<<" "<<node[i].right<<" "<<node[i].status<<" "

<<node[i].max<<" "<<node[i].lmax<<" "<<node[i].rmax<<endl;

}

*/

}

//system("pause");

}

Time Limit: 5000MS		Memory Limit: 30000K
Total Submissions: 1263		Accepted: 492