题目链接

P2894 [USACO08FEB] Hotel G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析

考虑用线段树维护区间信息

维护sum（最大连续空房间数）

如何合并？

sum1为max（sum2，sum3）（1的两个子区间）

但我们发现若区间为100 001（0表示空房间）

sum1=4而max（sum2，sum3）=2

所以再维护suml（从左开始的最长区间）、sumr（从右开始的最长区间），f（区间是否都为0）

维护上述信息即可

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=50005;
 5 
 6 int al[N*4][10];//1==sum,3==suml,4==sumr,6==f; 
 7 int lazy[N*4];
 8 
 9 void pushup(int id,int l,int r){
10     al[id][1]=max(al[id*2][4]+al[id*2+1][3],max(al[id*2][1],al[id*2+1][1]));
11     al[id][3]=al[id*2][3]; if(al[id*2][6]) al[id][3]+=al[id*2+1][3];
12     al[id][4]=al[id*2+1][4]; if(al[id*2+1][6]) al[id][4]+=al[id*2][4];
13     if(al[id*2][6]&&al[id*2+1][6]) al[id][6]=1;
14     else al[id][6]=0;//一定要更新 
15 }
16 
17 void pushdown(int id,int l,int r){
18     int m=l+(r-l)/2,v=lazy[id];
19     if(v!=2){
20         al[id*2][1]=al[id*2][3]=al[id*2][4]=(m-l+1)*v;
21         al[id*2][6]=v;
22         lazy[id*2]=v;
23         al[id*2+1][1]=al[id*2+1][3]=al[id*2+1][4]=(r-m)*v;
24         al[id*2+1][6]=v;
25         lazy[id*2+1]=v;
26         lazy[id]=2;
27     }
28 }
29 
30 void bu(int id,int l,int r){
31     lazy[id]=2;
32     if(l==r){
33         al[id][1]=al[id][3]=al[id][4]=al[id][6]=1;
34         return;
35     }
36     int m=l+(r-l)/2;
37     bu(id*2,l,m);
38     bu(id*2+1,m+1,r);
39     pushup(id,l,r);
40 }
41 
42 void add(int id,int l,int r,int s,int t,int v){
43     if(s<=l&&r<=t){
44         al[id][1]=al[id][3]=al[id][4]=(r-l+1)*v;
45         al[id][6]=v;
46         lazy[id]=v;
47         return;
48     }
49     pushdown(id,l,r);
50     int m=l+(r-l)/2;
51     if(s<=m) add(id*2,l,m,s,t,v);
52     if(t>=m+1) add(id*2+1,m+1,r,s,t,v);
53     pushup(id,l,r);
54 }
55 
56 int ask(int id,int l,int r,int x){
57     pushdown(id,l,r);
58     if(l==r) return l;
59     int m=l+(r-l)/2;
60     if(al[id*2][1]>=x) return ask(id*2,l,m,x);
61     else if(al[id*2][4]+al[id*2+1][3]>=x) return m-al[id*2][4]+1;
62     else return ask(id*2+1,m+1,r,x);
63 }
64 
65 int main(){
66     int n,m;
67     scanf("%d %d", &n, &m);
68     bu(1,1,n);
69     
70     for(int i=1;i<=m;i++){
71         int que,x,y;
72         scanf("%d", &que);
73         if(que==1){
74             scanf("%d", &x);
75             if(al[1][1]<x){
76                 cout<<0<<endl;
77                 continue;
78             }
79             y=ask(1,1,n,x);
80             cout<<y<<endl;
81             add(1,1,n,y,y+x-1,0);
82         }
83         else{
84             scanf("%d %d", &x, &y);
85             add(1,1,n,x,x+y-1,1);
86         }
87     }
88     return 0;
89 }