有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;}新聞熱點
疑難解答
