經(jīng)典線段樹的題。

     每個(gè)節(jié)點(diǎn)存儲(chǔ)的信息：左端點(diǎn)連續(xù)空房間的長(zhǎng)度，右端點(diǎn)連續(xù)空房間長(zhǎng)度，連續(xù)空房間的最大長(zhǎng)度。

     由于要求每次必須從盡量靠左邊的位置進(jìn)行居住，那么搜索時(shí)應(yīng)盡量讓區(qū)間起始位置更小：

1.如果當(dāng)前區(qū)間的最大空房間長(zhǎng)度小于要尋找的長(zhǎng)度，說明不會(huì)找到符合的區(qū)間，直接退出。

2.如果左子區(qū)間的最大空房間長(zhǎng)度大于等于要尋找的長(zhǎng)度，那么應(yīng)該進(jìn)入左子區(qū)間查找。

3.否則，如果左子區(qū)間的右端點(diǎn)連續(xù)空房間長(zhǎng)度 + 右子區(qū)間的左端點(diǎn)連續(xù)空房間的長(zhǎng)度 大于等于要尋找的長(zhǎng)度則直接返回左子區(qū)間右端點(diǎn)起始空房間下標(biāo)。

4.否則，進(jìn)入右區(qū)間尋找。

AC代碼：

#include<cstdio>#include<algorithm>using namespace std;const int maxn = 2e5;struct node{	int l, r;	int len, lenl, lenr;	int tag; //0代表全空  1代表全滿 -1代表混雜 }t[maxn];void build(int l, int r, int cur){	t[cur].l = l, t[cur].r = r;	t[cur].len = t[cur].lenl = t[cur].lenr = r - l + 1;	t[cur].tag = 0; 	if(l == r) return;	int mid = (l + r) / 2;	build(l, mid, cur << 1);	build(mid + 1, r, (cur << 1) + 1);}void lazy(int cur){   	if(t[cur].l == t[cur].r) return;	if(t[cur].tag >= 0) {  //覆蓋 		int l = cur << 1, r = (cur << 1) + 1;		int val;		if(t[cur].tag == 0) val = t[l].r - t[l].l + 1;		else val = 0;		t[l].len = t[l].lenl = t[l].lenr = val;				if(t[cur].tag == 0) val = t[r].r - t[r].l + 1;		else val = 0;		t[r].len = t[r].lenl = t[r].lenr = val;		t[r].tag = t[l].tag = t[cur].tag;	}}int search(int len, int cur){	if(t[cur].len < len) return 0;	int l = t[cur].l, r = t[cur].r;	if(l == r) return l;	lazy(cur);	if(t[cur << 1].len >= len) return search(len, cur << 1);	else if(t[cur << 1].lenr + t[(cur << 1) + 1].lenl >= len) return t[cur << 1].r - t[cur << 1].lenr + 1;	else if(t[(cur << 1) + 1].len >= len) return search(len, (cur << 1) +1);}void update(int l, int r, int tag, int cur){	int l1 = t[cur].l, r1 = t[cur].r;	if(l1 == l && r1 == r){		t[cur].tag = tag;		int val;		if(tag) val = 0;		else val = r1 - l1 + 1;		t[cur].len = t[cur].lenl = t[cur].lenr = val;		return;	}	lazy(cur);	int mid = (l1 + r1) / 2;	if(r <= mid) update(l, r, tag, cur << 1);	else if(l >= mid + 1) update(l, r, tag, (cur << 1) + 1);	else {		update(l, mid, tag, cur << 1);		update(mid + 1, r, tag, (cur << 1) + 1);	}		int c1 = cur << 1, c2 = (cur << 1) + 1;	int w = t[c1].lenr + t[c2].lenl;	t[cur].lenl = t[c1].lenl, t[cur].lenr = t[c2].lenr;	if(t[c1].tag == 0) t[cur].lenl = w;	if(t[c2].tag == 0) t[cur].lenr = w;	t[cur].len = max(t[c1].len, t[c2].len);	t[cur].len = max(w, t[cur].len);	t[cur].len = max(t[cur].len, t[cur].lenr);	t[cur].len = max(t[cur].len, t[cur].lenl);	if(t[cur].len == 0) t[cur].tag = 1;	else if(t[cur].len == r1 - l1 + 1) t[cur].tag = 0;	else t[cur].tag = -1;}int main(){	int n,q;	while(scanf("%d%d", &n, &q) == 2){		build(1, n, 1);		int a, b, c;		for(int i = 0; i < q; ++i){			scanf("%d", &a);			if(a == 1){				scanf("%d", &b);				int x = search(b, 1);				PRintf("%d/n", x);				if(x != 0) update(x, x + b - 1, 1, 1);			}			else {				scanf("%d%d", &b, &c);				update(b, b + c - 1, 0, 1);			}		}	}	return 0;}如有不當(dāng)之處歡迎指出！