POJ 1823 Hotel (线段树)

Hotel

Time Limit: 5000MS		Memory Limit: 30000K
Total Submissions: 1584		Accepted: 645

Description

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.

Input

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

Output

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.

Sample Input

Sample Output

Source

Romania OI 2002

题意：有三种操作
c A M  如果c = 1 表示从 A 到 A+M-1 住进M个人
c A M  如果c = 2 表示从 A 到 A+M-1 搬到M个人
c      如果c = 3 表示查询这个hotel 连续的空房间有多少

以前求连续最长线段总要新建一个数组重新统计，原来还有以下这种比较那个的做法，学习了。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)

const int N=16010;

struct node{
    int l,r,cover;  //1表示住满人，-1表示空 0表示非满非空
    int lma,rma,len;    //lma左连续的人数，rma右连续的人数，len 是node[u]的最大连续人数
}tree[N*3];

void build(int l,int r,int rt){
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    build(l,mid,L(rt));
    build(mid+1,r,R(rt));
}

void PushDown(int op,int rt){
    if(op==-1){
        tree[rt].cover=0;
        tree[L(rt)].cover=op;
        tree[L(rt)].len=tree[L(rt)].lma=tree[L(rt)].rma=tree[L(rt)].r-tree[L(rt)].l+1;
        tree[R(rt)].cover=op;
        tree[R(rt)].len=tree[R(rt)].lma=tree[R(rt)].rma=tree[R(rt)].r-tree[R(rt)].l+1;
    }else{
        tree[rt].cover=0;
        tree[L(rt)].cover=op;
        tree[L(rt)].len=tree[L(rt)].lma=tree[L(rt)].rma=0;
        tree[R(rt)].cover=op;
        tree[R(rt)].len=tree[R(rt)].lma=tree[R(rt)].rma=0;
    }
}

void update(int op,int l,int r,int rt){
    if(tree[rt].l==l && tree[rt].r==r){
        tree[rt].cover=op;
        if(op==1)
            tree[rt].len=tree[rt].lma=tree[rt].rma=0;
        else
            tree[rt].len=tree[rt].lma=tree[rt].rma=tree[rt].r-tree[rt].l+1;
        return ;
    }
    if(tree[rt].cover==op)
        return ;
    if(tree[rt].cover==-op)  //又是延迟覆盖
        PushDown(-op,rt);
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if(r<=mid)
        update(op,l,r,L(rt));
    else if(l>=mid+1)
        update(op,l,r,R(rt));
    else{
        update(op,l,mid,L(rt));
        update(op,mid+1,r,R(rt));
    }                       
    if(tree[L(rt)].cover==-1)   //原来可以用这种方法来求连续线段
        tree[rt].lma=tree[L(rt)].len+tree[R(rt)].lma;
    else
        tree[rt].lma=tree[L(rt)].lma;
    if(tree[R(rt)].cover==-1)
        tree[rt].rma=tree[R(rt)].len+tree[L(rt)].rma;
    else
        tree[rt].rma=tree[R(rt)].rma;

    int mid_num=tree[L(rt)].rma+tree[R(rt)].lma;
    int a=max(tree[rt].lma,tree[rt].rma);
    int b=max(tree[L(rt)].len,tree[R(rt)].len);
    tree[rt].len=max(max(a,b),mid_num);
    if(tree[L(rt)].cover==tree[R(rt)].cover)    //递归回来修改父亲结点的信息
        tree[rt].cover=tree[L(rt)].cover;
}

int main(){

    //freopen("input.txt","r",stdin);

    int n,p;
    while(~scanf("%d%d",&n,&p)){
        build(1,n,1);
        tree[1].cover=-1;
        tree[1].len=n;
        int op,src,m;
        while(p--){
            scanf("%d",&op);
            if(op==1){
                scanf("%d%d",&src,&m);
                update(1,src,src+m-1,1);
            }else if(op==2){
                scanf("%d%d",&src,&m);
                update(-1,src,src+m-1,1);
            }else
                printf("%d\n",tree[1].len);
        }
    }
    return 0;
}