有n个房间和k个操作，最开始全部为空。操作1：输入一个数d，找出连续d个空房间，输出起点房间编号。若有多个输出最小的，如果不存在输出0。操作2：输入两个数x和d，清空从x开始的d个房间。
10 6 1 3 1 3 1 3 1 3 2 5 5 1 6
1 4 7 0 5
用线段树维护，每个节点存储三个值msum，lsum，rsum。msum表示当前区间最长的连续空房间数量；lsum表示当前区间[l,r]中从l开始连续向右空房间数量；rsum表示当前区间[l,r]中从r开始连续向左空房间数量。 主要的操作集中在如何更新父节点（也就是区间合并操作）。
首先，把左孩子的lsum赋给自己的lsum，rsum同理。
lsum[rt] = lsum[rt<<1];rsum[rt] = rsum[rt<<1|1];这时候如果左孩子全部为空，则可以和右孩子左侧的空房间连接在一起。同理，如果右孩子全部为空，则可以和左孩子右侧德空房间连接在一起。
if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1]; if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1];msum有两三种计算方法：空房间全部在左孩子；空房间全部在右孩子；空房间从左孩子的右侧到右孩子的左侧。
msum[rt] = max(lsum[rt<<1|1]+rsum[rt<<1],max(msum[rt<<1],msum[rt<<1|1]));这就是区间合并的写法：
void pushup(int rt,int m) //更新父节点 { lsum[rt] = lsum[rt<<1]; rsum[rt] = rsum[rt<<1|1]; if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1]; //若左孩子全为空 则和右孩子合并 if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1]; msum[rt] = max(lsum[rt<<1|1]+rsum[rt<<1],max(msum[rt<<1],msum[rt<<1|1]));//左孩子或右孩子或在中间合并 }查询时，也是分为三种情况： 空房间全部在左孩子：if (msum[rt<<1] >= w) return query(w,lson); 空房间横跨左孩子和右孩子：if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return mid - rsum[rt<<1] + 1; 空房间全部在右孩子：return query(w,rson);
完整代码：
#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 1000000#define lson l,mid,rt << 1#define rson mid+1,r,rt << 1 | 1using namespace std;int n,m,op,a,b;int lsum[N],rsum[N],msum[N],cover[N];void build(int l,int r,int rt) //msum当前区间最长连续空 l/rsum前缀/后缀最长连续空 { msum[rt] = lsum[rt] = rsum[rt] = r - l + 1; cover[rt] = -1; if (l == r) return; int mid = (l + r) >> 1; build(lson); build(rson);}void pushdown(int rt,int m) //标记下传 { if (cover[rt] != -1) { cover[rt<<1] = cover[rt<<1|1] = cover[rt]; if (cover[rt] == 0) msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = m - (m >> 1); else msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = 0; if (cover[rt] == 0) msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = m >> 1; else msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = 0; cover[rt] = -1; }}void pushup(int rt,int m) //更新父节点 { lsum[rt] = lsum[rt<<1]; rsum[rt] = rsum[rt<<1|1]; if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1]; //若左孩子全为空 则和右孩子合并 if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1]; msum[rt] = max(lsum[rt<<1|1]+rsum[rt<<1],max(msum[rt<<1],msum[rt<<1|1]));//左孩子或右孩子或在中间合并 }void update(int L,int R,int c,int l,int r,int rt){ if (L <= l && r <= R) { if (c == 0) msum[rt] = lsum[rt] = rsum[rt] = r - l + 1; else msum[rt] = lsum[rt] = rsum[rt] = 0; cover[rt] = c; return; } pushdown(rt,r-l+1); int mid = (l + r) >> 1; if (L <= mid) update(L,R,c,lson); if (mid < R) update(L,R,c,rson); pushup(rt,r-l+1);}int query(int w,int l,int r,int rt){ if (l == r) return l; pushdown(rt,r-l+1); int mid = (l + r) >> 1; if (msum[rt<<1] >= w) return query(w,lson); else if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return mid - rsum[rt<<1] + 1; return query(w,rson); }int main(){ cin>>n>>m; build(1,n,1); while (m--) { cin>>op; if (op == 1) { scanf("%d",&a); if (msum[1] < a) cout<<0<<endl; else { int p = query(a,1,n,1); cout<<p<<endl; update(p,p+a-1,1,1,n,1); } } else { scanf("%d%d",&a,&b); update(a,a+b-1,0,1,n,1); } } return 0;}新闻热点
疑难解答
