题意：有很多房间，每次客人来住的时间要连续的房间，多次操作查询。
分析：维护prefix和suffix数组来表示一段区间连续的个数
具体实现详见代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define lson l , mid , rt << 1 #define rson mid + 1, r, rt << 1 | 1 using namespace std; const int maxn = 4e5 +20; struct InterxTree { int prefix[maxn],suffix[maxn],sum[maxn],set[maxn]; void build(int l, int r, int rt) { set[rt] = -1; prefix[rt] = suffix[rt] = sum[rt] = r - l + 1; if(l == r) return ; int mid = (l + r) >> 1; build(lson); build(rson); } void pushdown(int rt ,int k) { if(~set[rt]) { set[rt<<1] = set[rt<<1|1] = set[rt]; prefix[rt<<1] = suffix[rt<<1] = sum[rt<<1] = set[rt] ? 0 : k - (k>>1); prefix[rt<<1|1] = suffix[rt<<1|1] = sum[rt<<1|1] = set[rt] ? 0 : (k>>1); set[rt] = -1; } } void maintain(int rt ,int k) { suffix[rt] = suffix[rt<<1|1]; prefix[rt] = prefix[rt<<1]; if(prefix[rt<<1] == k - (k>>1)) prefix[rt] += prefix[rt<<1|1]; if(suffix[rt<<1|1] == (k>>1)) suffix[rt] += suffix[rt<<1]; sum[rt] = max(suffix[rt<<1] + prefix[rt<<1|1] , max(sum[rt<<1],sum[rt<<1|1])); } void update(int L, int R, int v, int l, int r, int rt) { if(L <= l && r <= R) { prefix[rt] = suffix[rt] = sum[rt] = v ? 0 : r - l + 1; set[rt] = v; return ; } pushdown(rt , r - l + 1); int mid = (l + r) >> 1; if(L <= mid) update(L, R , v, lson); if(R > mid) update(L, R , v, rson); maintain(rt , r - l + 1); } int query(int v, int l, int r, int rt) { if(l == r) return l; if(set[rt] == 0) return l; int mid = (l + r) >> 1; if(sum[rt<<1] >= v) return query(v, lson); else if(suffix[rt<<1] + prefix[rt<<1|1] >= v) return mid - suffix[rt<<1] + 1; else return query(v, rson); } }tree; int main(void) { freopen("1.txt","r",stdin); int n,m; while(~scanf("%d%d",&n,&m)) { tree.build(1,n,1); int a,b,c; while(m--) { scanf("%d",&a); if(a==1) { scanf("%d",&b); if(tree.sum[1] < b) { printf("0\n"); } else { int pos = tree.query(b , 1, n, 1); printf("%d\n",pos); tree.update(pos,pos + b - 1, 1, 1, n, 1); } } else { scanf("%d%d",&b,&c); tree.update(b, b + c - 1, 0, 1, n, 1); } } } return 0; }