|
|
題目鏈接：http://poj.org/problem?id=3667
  /**//*
 題意：
給出M(M <= 50000)組操作，每組操作的形式如下：
1 D: 詢問是否有長度為D的連續區間，如果存在輸出最左邊的，否則輸出0
，并且將這塊連續的區間占據。
2 X D:將從X開始的連續D塊空間釋放掉。
解法：
線段樹
思路：
線段樹染色問題，和ZJU 2301 Color the Ball類似，也是尋找最長連
續區間。線段樹中可以保存如下信息：
enum eKind{
EK_MULTIPLE = -1,
EK_EMPTY = 0, // 清空當前空間
EK_FULL = 1, // 填充當前空間
};
int root, l, r;
eKind cover; // 當前區間的種類的枚舉
int lMax; // 包含左區間的連續空閑區間的最大值
int rMax; // 包含右區間的連續空閑區間的最大值
int mMax; // 當前結點管轄區間的最大值
首先來看下問題對應的操作，查詢連續D區間這個我在后面會詳細介紹
，先來看看插入操作，題目中有兩種插入，一個是插入一塊滿的區間，另一
個是刪除一段固定長度的區間，其實原理是一樣的，我們只要用一個lazy標
記即可。我的結構中的lazy標記用eKind這個枚舉類型來表示。EK_EMPTY表示
清空一段區間，EK_FULL表示填充一段區間。每次插入操作只進行到當前區間
完全覆蓋結點區間時。如果完全覆蓋，則根據插入的eKind類型填充mMax、
lMax、rMax的信息，否則將當前結點有的lazy標記傳遞給兩個子結點，更新
他們的結點信息，然后遞歸左右兒子，繼續插入操作，遞歸返回時我們用以
下函數從左右兒子中得到當前結點的信息：
void UpdateBy(Tree* ls, Tree* rs);
之所以把它寫成函數是因為這里的處理比較麻煩，很容易出錯，并且需要
調用多次，這個函數的作用就是通過左右兒子的信息填充本身的信息。
信息一多，處理的時候就要極為小心，因為很容易出錯。
lMax表示當前結點的包含左閉區間的最優解。
rMax表示當前結點的包含右閉區間的最優解。
mMax則是當前區間的最優解。
這樣我們就可以通過傳遞性在兒子結點的屬性都得知的情況下將父親的值
計算出來，最后遞歸到根結點。具體的計算過程可以自己畫棵樹看一下，
然后是查詢操作，查詢的話首先判斷當前結點的最大值是否比給定的查
詢值小，如果是這樣直接返回0表示沒有找到。否則將當前值和左兒子的最大
值進行比較，如果滿足給定值小于等于左兒子的最大值則遞歸計算左兒子，
如果不是，則比較的不是右兒子，因為有可能這個最大空閑區間是在左兒子的
rMax + 右兒子的 lMax 上，因此需要和這個值比較，最后才是和右兒子的值
比較，這里可以保證肯定能找到一個解，需要注意的是在詢問的時候需要將當
前結點的lazy標記往下傳。
 */
 #include <iostream>
using namespace std;
#define maxn 50010
enum eKind {
EK_MULTIPLE = -1,
EK_EMPTY = 0, // 清空當前空間
EK_FULL = 1, // 填充當前空間
};
struct Tree {
int root, l, r;
eKind cover;
int mMax, lMax, rMax;
  int len() {
return r - l + 1;
 }
void CoverBy(eKind val);
void UpdateBy(Tree* ls, Tree* rs);
void TranslateToSon();
void TranslateTo(Tree* ts);
}T[maxn*4];
int MMax(int a, int b) {
return a > b ? a : b;
}
int MMax(int a, int b, int c, int d) {
return MMax(MMax(a, b), MMax(c, d));
}
void Tree::TranslateToSon() {
if(cover != EK_MULTIPLE) {
TranslateTo(&T[root<<1]);
TranslateTo(&T[root<<1|1]);
}
cover = EK_MULTIPLE;
}
void Tree::TranslateTo(Tree* ts) {
ts->CoverBy(cover);
}
void Tree::CoverBy(eKind val) {
cover = val;
if(val == EK_EMPTY) {
mMax = lMax = rMax = len();
}else if(val == EK_FULL) {
mMax = lMax = rMax = 0;
}
}
void Tree::UpdateBy(Tree* ls, Tree* rs) {
lMax = ls->lMax; if(lMax == ls->len()) lMax += rs->lMax;
rMax = rs->rMax; if(rMax == rs->len()) rMax += ls->rMax;
mMax = MMax(ls->mMax, rs->mMax);
mMax = MMax(mMax, ls->rMax + rs->lMax, lMax, rMax);
}
void Build(int root, int l, int r) {
T[root].root = root;
T[root].l = l;
T[root].r = r;
T[root].cover = EK_EMPTY;
T[root].mMax = T[root].lMax = T[root].rMax = T[root].len();
if(l == r) {
return ;
}
int mid = (l + r) >> 1;
Build(root<<1, l, mid);
Build(root<<1|1, mid+1, r);
}
void Insert(int root, int l, int r, eKind val) {
if(l > T[root].r || r < T[root].l)
return ;
if(l <= T[root].l && T[root].r <= r) {
T[root].CoverBy(val);
return ;
}
T[root].TranslateToSon();
Insert(root<<1, l, r, val);
Insert(root<<1|1, l, r, val);
T[root].UpdateBy(&T[root<<1], &T[root<<1|1]);
}
int Query(int root, int val) {
// 當前結點的最大連續塊小于要求的塊
if(val > T[root].mMax) {
return 0;
}
// 遞歸結束到元區間位置
if(T[root].l == T[root].r) {
if(val == 1) {
return T[root].l;
}
return 0;
}
T[root].TranslateToSon();
if(val <= T[root<<1].mMax) {
// 在左子樹中能找到最大塊
return Query(root<<1, val);
}else if(val <= T[root<<1].rMax + T[root<<1|1].lMax) {
// 在左右子樹的合并塊中找到
return (T[root<<1].r - T[root<<1].rMax + 1);
}else {
// 在右子樹中能找到最大塊
return Query(root<<1|1, val);
}
}
int n, m;
int main() {
int i;
while(scanf("%d %d", &n, &m) != EOF) {
Build(1, 1, n);
for(i = 0; i < m; i++) {
int op, x, y;
scanf("%d", &op);
if(op == 1) {
scanf("%d", &x);
int nPos = Query(1, x);
if(nPos) {
Insert(1, nPos, nPos + x - 1, EK_FULL);
}
printf("%d\n", nPos);
}else {
scanf("%d %d", &x, &y);
Insert(1, x, x + y - 1, EK_EMPTY);
}
}
}
return 0;
}
|