题目传送门(BZOJ)
>原文链接<

题解

线段树区间合并模板题, 稍复杂

设这样几个数组 : $siz、lsiz、rsiz、len、laz$

分别表示 区间最大连续长度从左开始的最大连续长度从右开始的区间最大连续长度区间总长度懒度标记

每个节点的$siz$就是两个儿子的$siz$和左儿子的$rsiz$+右儿子的$lsiz$取$\max$

对于$lsiz$的维护,若左儿子的$siz$等于len,那么就是左儿子$siz$加右儿子$lsiz$,否则是左儿子的$lsiz$

对于$rsiz$的类似。

本题输入有小坑,一次退房的$(x, y)$是从$x$到$x+y-1$

  对于每次查询,如果$siz[root] < query.K$ ,那么直接输出$0$即可,否则的话以 $siz[ls]>K$ ? $rsiz[ls]+lsiz[rs]$ ?$siz[rs]$ 的顺序选择递归,如果左子树不够大,而中间部分足够,那么我们可以直接返回$ans$

并从$ans+query$的区间范围对树进行修改, 区间覆盖然后$pushUp$即可.

代码

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ls p<<1#define rs p<<1|1#define lson l, m, p<<1#define rson m+1, r, p<<1|1#define im int mid = (l+r) >> 1using namespace std;const int N = 410000;int ans=0, n;struct SegTree { int lsz[N<<2], rsz[N<<2], siz[N<<2], laz[N<<2], len[N<<2]; void pushup(int p) { lsz[p]=(siz[ls]==len[ls]?len[ls]+lsz[rs]:lsz[ls]); rsz[p]=(siz[rs]==len[rs]?len[rs]+rsz[ls]:rsz[rs]); siz[p]=max(siz[ls], max(siz[rs], rsz[ls]+lsz[rs])); } void pushdown(int p) { if(laz[p]==1) { lsz[rs]=rsz[rs]=siz[rs]=lsz[ls]=rsz[ls]=siz[ls]=0; laz[ls]=laz[rs]=1; } else if(laz[p]==2) { lsz[rs]=rsz[rs]=siz[rs]=len[rs]; lsz[ls]=rsz[ls]=siz[ls]=len[ls]; laz[ls]=laz[rs]=2; } laz[p]=0; } void build(int l, int r, int p) { lsz[p]=rsz[p]=siz[p]=len[p]=r-l+1; if(l==r)return; im; build(l, mid, ls); build(mid+1, r, rs); } int query(int l, int r, int p, int x) { pushdown(p); if(l==r) return l; int m = (l+r)>>1; if(siz[ls]>=x) return query(lson, x); if(rsz[ls]+lsz[ls|1]>=x) return m-rsz[ls]+1; else return query(rson, x); } void change(int l, int r, int p, int x, int y, int c) { pushdown(p); if(x<=l&&y>=r) { if(c==1) siz[p]=lsz[p]=rsz[p]=0; else siz[p]=lsz[p]=rsz[p]=len[p]; laz[p]=c; return; } im; if(x<=mid) change(l, mid, ls, x, y, c); if(y>mid) change(mid+1, r, rs, x, y, c); pushup(p); }}Tr;int main() { int q; scanf("%d%d", &n, &q); Tr.build(1, n, 1); while (q--) { int opt, x, y, p; scanf("%d", &opt); if(opt==1) { scanf("%d", &x); if(Tr.siz[1]<x) { puts("0"); continue; } p = Tr.query(1, n, 1, x); printf("%d\n", p); Tr.change(1, n, 1, p, p+x-1, 1); } else { scanf("%d%d", &x, &y); Tr.change(1, n, 1, x, x+y-1, 2); } }}