题解:
这题非常经典啊似乎。。经典模型要记住啊。。
对于每个节点维护该区间里的最大的连续区间,然后我们就可以logn递归找最前面的一段。
那就维护mx(无限制),lmx(必须从左边开始),rmx(必须从右边开始)。
代码:
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 const int N=50010; 11 int n,m,tl; 12 struct trnode{ 13 int l,r,lc,rc,mx,lmx,rmx,len,lazy; 14 }t[2*N]; 15 16 int minn(int x,int y){ return x y ? x:y;} 18 19 int bt(int l,int r) 20 { 21 int x=++tl; 22 t[x].l=l;t[x].r=r; 23 t[x].lc=t[x].rc=0; 24 t[x].lazy=-1;t[x].len=r-l+1; 25 t[x].lmx=t[x].rmx=t[x].mx=t[x].len; 26 if(l mid) change(rc,l,r,d); 64 else 65 { 66 change(lc,l,mid,d); 67 change(rc,mid+1,r,d); 68 } 69 upd(x); 70 } 71 72 int query(int x,int len) 73 { 74 pd(x); 75 int k,lc=t[x].lc,rc=t[x].rc; 76 if(t[x].mx>=len) 77 { 78 if(t[x].lmx>=len) return t[x].l; 79 if((k=query(lc,len)) > 0) return k; 80 if(t[lc].rmx+t[rc].lmx>=len) return t[lc].r-t[lc].rmx+1; 81 if((k=query(rc,len)) > 0) return k; 82 } 83 return 0; 84 } 85 86 int main() 87 { 88 // freopen("a.in","r",stdin); 89 freopen("hotel.in","r",stdin); 90 freopen("hotel.out","w",stdout); 91 scanf("%d%d",&n,&m); 92 tl=0; 93 bt(1,n); 94 for(int i=1;i<=m;i++) 95 { 96 int tmp,x,len; 97 scanf("%d",&tmp); 98 if(tmp==1) 99 {100 scanf("%d",&len);101 x=query(1,len);102 printf("%d\n",x);103 if(x>0) change(1,x,x+len-1,1);104 }105 else 106 {107 scanf("%d%d",&x,&len);108 change(1,x,x+len-1,0);109 }110 }111 return 0;112 }