[cpp] /********************************************** 題目大意: 有一個旅館,有N個房間排成一排; 現在有兩種操作: 第一是有a個顧客要入住連續的a個房間; 要求輸出最小的左端點的位置,不能滿足就輸出0; 第二是將以a開始，長度為b的連續房間清空; 1 a: 詢問是不是有連續長度為a的空房間,有的話住進最左邊; 2 a b: 將[a,a+b-1]的房間清空; 算法思想: 記錄區間中最長的空房間 lsum表示區間左邊連續的空房個數; rsum表示區間右邊連續的空房個數; msum表示區間上最大的一段空房的長度; 算法過程： 如果1~n區間的msum值都比x小，就無解，否則有解; 對於每一個區間，如果它的左兒子的msum值大於等於x,則到左兒子裡去找; 如果左兒子的rsum加上右兒子的lsum大於等於x，則直接返回左兒子的右端點減去左兒子的rsum值; 否則到右兒子裡去找; ***********************************************/ #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<climits> #include<algorithm> using namespace std; #define L l , m , u << 1 #define R m + 1 , r , u << 1 | 1 const int N = 55555; int lsum[N<<2];//區間左邊連續的空房個數; int rsum[N<<2];//區間右邊連續的空房個數; int msum[N<<2];//區間上最大的一段空房的長度; int cover[N<<2]; void PushDown(int u,int m)//把當前結點的信息更新給兒子結點 { if (cover[u] != -1) { cover[u<<1] = cover[u<<1|1] = cover[u]; msum[u<<1] = lsum[u<<1] = rsum[u<<1] = cover[u] ? 0 : m - (m >> 1); msum[u<<1|1] = lsum[u<<1|1] = rsum[u<<1|1] = cover[u] ? 0 : (m >> 1); cover[u] = -1; } } void PushUp(int u,int m)//把當前結點的信息更新到父結點 { lsum[u] = lsum[u<<1]; rsum[u] = rsum[u<<1|1]; if(lsum[u] == m - (m >> 1)) lsum[u] += lsum[u<<1|1]; if(rsum[u] == (m >> 1)) rsum[u] += rsum[u<<1]; msum[u] = max(lsum[u<<1|1] + rsum[u<<1] , max(msum[u<<1] , msum[u<<1|1])); } void build(int l,int r,int u) { msum[u] = lsum[u] = rsum[u] = r - l + 1; cover[u] = -1; if (l == r) return; int m = (l + r) >> 1; build(L); build(R); } void update(int l1,int r1,int c,int l,int r,int u)//區間替換 { if (l1 <= l && r <= r1) { msum[u] = lsum[u] = rsum[u] = c ? 0 : r - l + 1; cover[u] = c; return ; } PushDown(u , r - l + 1); int m = (l + r) >> 1; if (l1 <= m) update(l1 , r1 , c , L); if (m < r1) update(l1 , r1 , c , R); PushUp(u , r - l + 1); } int query(int w,int l,int r,int u)//查詢滿足條件的最左斷點 { if (l == r) return l; PushDown(u , r - l + 1); int m = (l + r) >> 1; if (msum[u<<1] >= w)//左兒子的msum值大於等於x,則到左兒子裡去找; return query(w , L); else if (rsum[u<<1] + lsum[u<<1|1] >= w)//如果左兒子的rsum加上右兒子的lsum大於等於x，則直接返回左兒子的右端點減去左兒子的rsum值; return m - rsum[u<<1] + 1; return query(w , R);//否則到右兒子裡去找; } int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); int n , m; scanf("%d%d",&n,&m); build(1 , n , 1); while (m--) { int op , a , b; scanf("%d",&op); if (op == 1) { scanf("%d",&a); if (msum[1]<a) puts("0"); else { int p = query(a , 1 , n , 1); printf("%d\n",p); update(p , p + a - 1 , 1 , 1 , n , 1); } www.2cto.com } else { scanf("%d%d",&a,&b); update(a , a + b - 1 , 0 , 1 , n , 1); } } return 0; }
