|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2871
  /**//*
 題意：
現(xiàn)在有1到N(N <= 50000)個(gè)連續(xù)內(nèi)存塊，然后給出四種操作：
1. Reset 釋放所有內(nèi)存塊，并且輸出“Reset Now”。
2. New x 找到一塊有連續(xù)x塊內(nèi)存的空間，并且占據(jù)它。如果有多種，選擇起始數(shù)字
最小的，然后“New at A”，A表示起始數(shù)字；否則輸出“Reject New”。
3. Free x 釋放一塊占據(jù)x單元的內(nèi)存塊，并且輸出“Free from A to B”，A到B表示
占據(jù)的內(nèi)存塊；否則輸出“Reject Free”。
4. Get x 找到第x塊連續(xù)內(nèi)存，如果找到，輸出“Get at A”，A表示起始的數(shù)字單元
，如果當(dāng)前內(nèi)存塊小于x，則輸出“Reject Get”。
解法：
線段樹 + 樹狀數(shù)組
思路：
線段樹染色問題，和PKU 3667 Hotel類似，也是尋找最長(zhǎng)連續(xù)區(qū)間。線
段樹中可以保存如下信息：
enum eKind {
EK_MUTIPLE = -1, // 多種情況
EK_EMPTY = 0, // 當(dāng)前內(nèi)存塊全空
EK_FULL = 1, // 當(dāng)前內(nèi)存塊全滿
EK_LPOINT = 2, // 當(dāng)前內(nèi)存塊的左端點(diǎn)
};
int root, l, r;
eKind cover; // 當(dāng)前區(qū)間的種類的枚舉
int lMax; // 包含左區(qū)間的連續(xù)空閑區(qū)間的最大值
int rMax; // 包含右區(qū)間的連續(xù)空閑區(qū)間的最大值
int mMax; // 當(dāng)前結(jié)點(diǎn)管轄區(qū)間的最大值
int nCount; // 當(dāng)前區(qū)間分配好的內(nèi)存塊的數(shù)量
首先來看下問題對(duì)應(yīng)的操作，查詢連續(xù)D區(qū)間這個(gè)我在后面會(huì)詳細(xì)介紹
，先來看看插入操作，題目中有兩種插入，一個(gè)是插入一塊滿的區(qū)間，另一
個(gè)是刪除一段固定長(zhǎng)度的區(qū)間，其實(shí)原理是一樣的，我們只要用一個(gè)lazy標(biāo)
記即可。我的結(jié)構(gòu)中的lazy標(biāo)記用eKind這個(gè)枚舉類型來表示。EK_EMPTY表示
清空一段區(qū)間，EK_FULL表示填充一段區(qū)間。每次插入操作只進(jìn)行到當(dāng)前區(qū)間
完全覆蓋結(jié)點(diǎn)區(qū)間時(shí)。如果完全覆蓋，則根據(jù)插入的eKind類型填充mMax、
lMax、rMax的信息，否則將當(dāng)前結(jié)點(diǎn)有的lazy標(biāo)記傳遞給兩個(gè)子結(jié)點(diǎn)，更新
他們的結(jié)點(diǎn)信息，然后遞歸左右兒子，繼續(xù)插入操作，遞歸返回時(shí)我們用以
下函數(shù)從左右兒子中得到當(dāng)前結(jié)點(diǎn)的信息：
void UpdateBy(Tree* ls, Tree* rs);
之所以把它寫成函數(shù)是因?yàn)檫@里的處理比較麻煩，很容易出錯(cuò)，并且需要
調(diào)用多次，這個(gè)函數(shù)的作用就是通過左右兒子的信息填充本身的信息。
信息一多，處理的時(shí)候就要極為小心，因?yàn)楹苋菀壮鲥e(cuò)。
lMax表示當(dāng)前結(jié)點(diǎn)的包含左閉區(qū)間的最優(yōu)解。
rMax表示當(dāng)前結(jié)點(diǎn)的包含右閉區(qū)間的最優(yōu)解。
mMax則是當(dāng)前區(qū)間的最優(yōu)解。
這樣我們就可以通過傳遞性在兒子結(jié)點(diǎn)的屬性都得知的情況下將父親的值
計(jì)算出來，最后遞歸到根結(jié)點(diǎn)。具體的計(jì)算過程可以自己畫棵樹看一下。
然后是查詢操作，查詢的話首先判斷當(dāng)前結(jié)點(diǎn)的最大值是否比給定的查
詢值小，如果是這樣直接返回0表示沒有找到。否則將當(dāng)前值和左兒子的最大
值進(jìn)行比較，如果滿足給定值小于等于左兒子的最大值則遞歸計(jì)算左兒子，
如果不是，則比較的不是右兒子，因?yàn)橛锌赡苓@個(gè)最大空閑區(qū)間是在左兒子的
rMax + 右兒子的 lMax 上，因此需要和這個(gè)值比較，最后才是和右兒子的值
比較，這里可以保證肯定能找到一個(gè)解，需要注意的是在詢問的時(shí)候需要將當(dāng)
前結(jié)點(diǎn)的lazy標(biāo)記往下傳。
以上操作可以處理New操作，F(xiàn)ree操作可以用樹狀數(shù)組來統(tǒng)計(jì)，我們把每次
New一塊空間的時(shí)候，將連續(xù)塊的左端點(diǎn)標(biāo)記為EK_LPOINT，nCount則記為1，這
樣通過兒子結(jié)點(diǎn)計(jì)算父親的nCount值只需要將左右兒子的nCount域相加即可。
然后Get操作和Free操作是類似的，也需要找到第K塊內(nèi)存塊，二分這個(gè)K，然后
找到滿足條件的最小值即可。
 */
#include <iostream>
using namespace std;
#define maxn 50010
int n;
enum eKind  {
EK_MUTIPLE = -1, // 多種情況
EK_EMPTY = 0, // 當(dāng)前內(nèi)存塊全空
EK_FULL = 1, // 當(dāng)前內(nèi)存塊全滿
EK_LPOINT = 2, // 當(dāng)前內(nèi)存塊的左端點(diǎn)
};
struct Tree {
int root, l, r;
int mMax; // 當(dāng)前結(jié)點(diǎn)下最大空閑塊
int lMax; // 左連接最大空閑塊
int rMax; // 右連接最大空閑塊
int nCount; // 當(dāng)前結(jié)點(diǎn)下占據(jù)內(nèi)存塊的次數(shù)
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;
// 遞歸結(jié)束到元區(qū)間位置
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;
}
|