|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2871
  /**//*
 題意：
現在有1到N(N <= 50000)個連續內存塊，然后給出四種操作：
1. Reset 釋放所有內存塊，并且輸出“Reset Now”。
2. New x 找到一塊有連續x塊內存的空間，并且占據它。如果有多種，選擇起始數字
最小的，然后“New at A”，A表示起始數字；否則輸出“Reject New”。
3. Free x 釋放一塊占據x單元的內存塊，并且輸出“Free from A to B”，A到B表示
占據的內存塊；否則輸出“Reject Free”。
4. Get x 找到第x塊連續內存，如果找到，輸出“Get at A”，A表示起始的數字單元
，如果當前內存塊小于x，則輸出“Reject Get”。
解法：
線段樹 + 樹狀數組
思路：
線段樹染色問題，和PKU 3667 Hotel類似，也是尋找最長連續區間。線
段樹中可以保存如下信息：
enum eKind {
EK_MUTIPLE = -1, // 多種情況
EK_EMPTY = 0, // 當前內存塊全空
EK_FULL = 1, // 當前內存塊全滿
EK_LPOINT = 2, // 當前內存塊的左端點
};
int root, l, r;
eKind cover; // 當前區間的種類的枚舉
int lMax; // 包含左區間的連續空閑區間的最大值
int rMax; // 包含右區間的連續空閑區間的最大值
int mMax; // 當前結點管轄區間的最大值
int nCount; // 當前區間分配好的內存塊的數量
首先來看下問題對應的操作，查詢連續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標記往下傳。
以上操作可以處理New操作，Free操作可以用樹狀數組來統計，我們把每次
New一塊空間的時候，將連續塊的左端點標記為EK_LPOINT，nCount則記為1，這
樣通過兒子結點計算父親的nCount值只需要將左右兒子的nCount域相加即可。
然后Get操作和Free操作是類似的，也需要找到第K塊內存塊，二分這個K，然后
找到滿足條件的最小值即可。
 */
#include <iostream>
using namespace std;
#define maxn 50010
int n;
enum eKind  {
EK_MUTIPLE = -1, // 多種情況
EK_EMPTY = 0, // 當前內存塊全空
EK_FULL = 1, // 當前內存塊全滿
EK_LPOINT = 2, // 當前內存塊的左端點
};
struct Tree {
int root, l, r;
int mMax; // 當前結點下最大空閑塊
int lMax; // 左連接最大空閑塊
int rMax; // 右連接最大空閑塊
int nCount; // 當前結點下占據內存塊的次數
eKind lazy_cover;
  int len() {
return r - l + 1;
 }
void CoverBy(eKind eVal);
void TranslateTo(Tree *ts);
void TranslateToSon();
void UpdateBy(Tree* ls, Tree* rs);
}T[maxn*6];
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::CoverBy(eKind eVal) {
lazy_cover = eVal;
if(eVal == EK_EMPTY) {
nCount = 0;
mMax = lMax = rMax = len();
}else if(eVal == EK_FULL) {
nCount = 0;
mMax = lMax = rMax = 0;
}else if(eVal == EK_LPOINT) {
nCount = 1;
mMax = lMax = rMax = 0;
}
}
void Tree::TranslateTo(Tree *ts) {
ts->CoverBy(lazy_cover);
}
void Tree::TranslateToSon() {
if(lazy_cover != EK_MUTIPLE) {
TranslateTo(&T[root<<1]);
TranslateTo(&T[root<<1|1]);
lazy_cover = EK_MUTIPLE;
}
}
void Tree::UpdateBy(Tree* ls, Tree* rs) {
nCount = ls->nCount + rs->nCount;
lMax = ls->lMax; if(lMax == ls->len()) lMax += rs->lMax;
rMax = rs->rMax; if(rMax == rs->len()) rMax += ls->rMax;
mMax = MMax(lMax, rMax);
mMax = MMax(mMax, ls->mMax, rs->mMax, ls->rMax + rs->lMax);
}
void Build(int root, int l, int r) {
T[root].root = root;
T[root].l = l;
T[root].r = r;
T[root].CoverBy(EK_EMPTY);
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 QueryNew(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 QueryNew(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 QueryNew(root<<1|1, val);
}
}
bool IsEmpty(int root, int pos) {
if(pos < T[root].l || pos > T[root].r)
return false;
if(pos == T[root].l && T[root].r == pos) {
return T[root].mMax;
}
T[root].TranslateToSon();
return IsEmpty(root<<1, pos) || IsEmpty(root<<1|1, pos);
}
int Count(int root, int l, int r) {
if(l > T[root].r || r < T[root].l)
return 0;
if(l <= T[root].l && T[root].r <= r)
return T[root].nCount;
T[root].TranslateToSon();
return Count(root<<1, l, r) + Count(root<<1|1, l, r);
}
int FindKCount(int K) {
int l = 1;
int r = n;
int ans = n + 1;
while(l <= r) {
int m = (l + r) >> 1;
if(Count(1, 1, m) >= K) {
r = m - 1;
ans = m;
}else
l = m + 1;
}
return ans;
}
int m;
int main() {
int i;
char str[10];
while(scanf("%d %d", &n, &m) != EOF) {
Build(1, 1, n);
for(i = 0; i < m; i++) {
scanf("%s", str);
if(!strcmp(str, "Reset")) {
Insert(1, 1, n, EK_EMPTY);
printf("Reset Now\n");
}else {
int x;
scanf("%d", &x);
if(!strcmp(str, "New")) {
int pos = QueryNew(1, x);
if(pos) {
printf("New at %d\n", pos);
Insert(1, pos, pos + x - 1, EK_FULL);
Insert(1, pos, pos, EK_LPOINT);
}else
printf("Reject New\n");
}else if(!strcmp(str, "Free")) {
if(IsEmpty(1, x)) {
printf("Reject Free\n");
}else {
int K = Count(1, 1, x);
int l = FindKCount(K);
int r = FindKCount(K+1) - 1;
int st = l;
int ed = r;
while(l <= r) {
int m = (l + r) >> 1;
if(!IsEmpty(1, m)) {
l = m + 1;
ed = m;
}else
r = m - 1;
}
l = st;
r = ed;
printf("Free from %d to %d\n", l, r);
Insert(1, l, r, EK_EMPTY);
}
}else {
int K = FindKCount(x);
if(K == n + 1)
printf("Reject Get\n");
else
printf("Get at %d\n", K);
}
}
}
puts("");
}
return 0;
}
|