题意是这样的。
一个旅馆有N个客房。
有两种指令
1、分配长度为L的连续客房，尽量分配起始房间号小的
2、将[S,E]区间内退房
对于第一种指令，我们需要在线段树里维护3个域：lmax（与左端点相连的最长段）,rmax（与右端点相连的最长段）,max（总最长段）
转移的时候如果左区间的lmax>need，则在左区间内寻找；如果左区间的rmax+右区间的lmax>need，那么在左区间和右区间里共同分配，否则在右区间内分配
还有一些细节，就不赘述了。
贴代码
1
# include <cstdio>
2# include <cstring>
3# include <queue>
4# include <cstdlib>
5# include <vector>
6using namespace std;
7priority_queue<int,vector<int>,greater<int> > refer;
8struct node
9
{
10
int t,num;
11 char op;
12
};
13vector<node> data;
14int main()
15{
16 char str[100];
17 for(int i=1;i<=30000;i++)
18 refer.push(i);
19 int c[30001];
20 memset(c,0,sizeof(c));
21 while(gets(str))
22
{
23 node tmp;
24 tmp.t=atoi(strtok(str," "));
25 tmp.op=*strtok(NULL," ");
26 if(tmp.op=='.')
27 tmp.num=atoi(strtok(NULL," "));
28 data.push_back(tmp);
29
}
30 int now=0,last=0;
31 for(now=0;now<data.size();now++)
32 {
33 while(data[now].t-data[last].t>=600)
34 {
35 if(c[data[last].num]&&data[now].t-c[data[last].num]>=600)
36 {
37 refer.push(data[last].num);
38 c[data[last].num]=0;
39 }
40 last++;
41 }
42 switch(data[now].op)
43 {
44 case '+':
45 c[refer.top()]=data[now].t;
46 printf("%d\n",refer.top());
47 data[now].num=refer.top();
48 refer.pop();
49 break;
50 case '.':
51 if(c[data[now].num])
52 {
53 printf("+\n");
54 c[data[now].num]=data[now].t;
55 }
56 else
57 printf("-\n");
58 break;
59 };
60
61 }
62 //system("pause");
63 return 0;
64}
65
66