本文共 4803 字，大约阅读时间需要 16 分钟。
1、
2、题目大意;
一个宾馆要开发一个系统，该系统允许三种操作，第一种就是有n个旅客要住房，从m开始，连着住n个，另一种就是易组旅客要离开宾馆，退n个房间，是从i开始的连续n个房间，第三种也就是要输出的，老板随时问该宾馆现在可以接多大的组，也就是说空着的区间最长是多少
3、题目：
| Time Limit: 5000MS | | Memory Limit: 30000K |
| Total Submissions: 1872 | | Accepted: 787 |
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
12 1031 2 31 9 432 2 132 9 232 3 23
Sample Output
1244610
Source
4、AC代码：
#include #include using namespace std;#define N 16005struct node{ int l; int r; int lsum,rsum,msum; int flag; void cal() { lsum=rsum=msum=(r-l+1)*flag; }} a[N*4];void build(int l,int r,int rt){ a[rt].l=l; a[rt].r=r; a[rt].flag=1; a[rt].cal(); if(l==r) return ; int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1);}void update(int L,int R,int rt,int flag){ //printf("******%d %d %d %d %d\n",L,R,rt,a[rt].l,a[rt].r); if(L<=a[rt].l && R>=a[rt].r) { a[rt].flag=flag; a[rt].cal(); return ; } if(a[rt].flag!=-1) { a[rt<<1].flag=a[rt<<1|1].flag=a[rt].flag; a[rt<<1].cal(); a[rt<<1|1].cal(); a[rt].flag=-1; } int m=(a[rt].l+a[rt].r)>>1; if(R<=m) update(L,R,rt<<1,flag); else if(L>m) update(L,R,rt<<1|1,flag); else { update(L,m,rt<<1,flag); update(m+1,R,rt<<1|1,flag); } //如果左孩子的左边空的等于线段长度，说明整个左孩子都是空的， if(a[rt<<1].lsum==a[rt<<1].r-a[rt<<1].l+1) a[rt].lsum=a[rt<<1].lsum+a[rt<<1|1].lsum; else a[rt].lsum=a[rt<<1].lsum; //如果右孩子的右边空的等于线段长度，说明整个右孩子都是空的， if(a[rt<<1|1].rsum==a[rt<<1|1].r-a[rt<<1|1].l+1) a[rt].rsum=a[rt<<1|1].rsum+a[rt<<1].rsum; else a[rt].rsum=a[rt<<1|1].rsum; //更新中间的值 a[rt].msum=max(max(a[rt<<1].msum,a[rt<<1|1].msum),a[rt<<1].rsum+a[rt<<1|1].lsum);}int main(){ int n,p,x,b,c; scanf("%d%d",&n,&p); build(1,n,1); for(int i=1; i<=p; i++) { scanf("%d",&x); if(x==1) { scanf("%d%d",&b,&c); update(b,b+c-1,1,0); //printf("*\n"); } else if(x==2) { scanf("%d%d",&b,&c); update(b,b+c-1,1,1); } else if(x==3) { printf("%d\n",a[1].msum); } } return 0;}
转载地址：http://ggddi.baihongyu.com/