|
|
題目鏈接： http://poj.org/problem?id=2892
  /**//*
 題意：
給出M(M <= 50000)組操作，每組操作的形式如下：
1 D x: 將第x個村莊摧毀
2 Q x: 詢問和第x個村莊直接或者間接連接的村莊數目
3 R: 修復上一個被摧毀的村莊
解法：
線段樹 或者 樹狀數組
思路：
線段樹染色問題，和ZJU 2301 Color the Ball類似，也是尋找最長連
續區間。但是這題要簡單的多，因為插入的時候是對點操作，不需要用到
lazy標記，線段樹中可以保存如下信息：
enum eKind {
EK_BLACK = 0,
EK_WHITE = 1,
};
int root, l, r;
int lMax; // 包含左區間的連續空閑區間的最大值
int rMax; // 包含右區間的連續空閑區間的最大值
int mMax; // 當前結點管轄區間的最大值
首先來看下問題對應的操作，題目中有兩種插入，一個是插入一個摧毀
的村莊，另一個是插入一個修復的村莊，其實原理是一樣的。只不過這兩種
類型更新lMax，rMax，mMax的時候稍有不同，每次插入到線段樹元區間時，
根據插入的eKind類型填充mMax、lMax、rMax的信息，否則更新他們的結點
信息，然后遞歸左右兒子，繼續插入操作，遞歸返回時我們用以下函數從左
右兒子中得到當前結點的信息：
void UpdateBy(Tree* ls, Tree* rs);
之所以把它寫成函數是因為這里的處理比較麻煩，很容易出錯，并且需要
調用多次，這個函數的作用就是通過左右兒子的信息填充本身的信息。
信息一多，處理的時候就要極為小心，因為很容易出錯。
lMax表示當前結點的包含左閉區間的最優解。
rMax表示當前結點的包含右閉區間的最優解。
mMax則是當前區間的最優解。
這樣我們就可以通過傳遞性在兒子結點的屬性都得知的情況下將父親的值
計算出來，最后遞歸到根結點。具體的計算過程可以自己畫棵樹看一下，
然后是查詢操作，查詢的話首先來看遞歸出口，我們用兩個引用來表示
當前查到的信息是否左連通以及是否右連通，那么如果到元區間的時候當前
點的mMax是0，那么直接左右連通標記都標記為false，否則為true。如果不
是元區間，則判斷當前點在左兒子還是右兒子，如果在左兒子，那么遞歸左
右子，回歸時根據返回的引用值判斷當前是否右連通，如果右連通，那么將
右兒子的lMax值加到答案上來，再判斷lMax是否等于右兒子的len，如果不
相等說明下次回歸上去的時候必然不是右連通，標記置為false，對于右兒子
的情況做相同處理即可。回歸到根結點就是最后的答案了。
這題還可以用樹狀數組來做，寫起來也比較方便，還是利用成段求和來
統計當前點區間內的K大值，K值用二分枚舉即可。
 */
 #include <iostream>
using namespace std;
#define maxn 50010
enum eKind  {
EK_BLACK = 0,
EK_WHITE = 1,
};
struct Tree {
int root, l, r;
int lMax, rMax, mMax;
void CoverBy(eKind ek);
void UpdateBy(Tree* ls, Tree* rs);
  int len() {
return r - l + 1;
 }
}T[4*maxn];
void Build(int p, int l, int r) {
T[p].root = p;
T[p].l = l;
T[p].r = r;
T[p].rMax = T[p].lMax = T[p].mMax = T[p].len();
if(l == r)
return ;
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
}
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::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(lMax, rMax);
mMax = MMax(mMax, ls->mMax, rs->mMax, ls->rMax + rs->lMax);
}
void Tree::CoverBy(eKind ek) {
mMax = lMax = rMax = (ek==EK_WHITE) ? len() : 0;
}
void Insert(int p, int pos, eKind ek) {
if(pos > T[p].r || pos < T[p].l)
return ;
if(T[p].l == pos && pos == T[p].r) {
T[p].CoverBy(ek);
return ;
}
Insert(p<<1, pos, ek);
Insert(p<<1|1, pos, ek);
T[p].UpdateBy(&T[p<<1], &T[p<<1|1]);
}
int Query(int p, int pos, bool& lc, bool& rc) {
if(T[p].l == pos && pos == T[p].r) {
lc = rc = T[p].mMax;
return T[p].mMax;
}
int x;
if(pos <= T[p<<1].r) {
x = Query(p<<1, pos, lc, rc);
if(rc) {
x += T[p<<1|1].lMax;
if(T[p<<1|1].lMax < T[p<<1|1].len())
rc = false;
}
}else {
x = Query(p<<1|1, pos, lc, rc);
if(lc) {
x += T[p<<1].rMax;
if(T[p<<1].rMax < T[p<<1].len())
lc = false;
}
}
return x;
}
int n, m;
int stack[maxn], top;
int main() {
char str[5];
int x;
while(scanf("%d %d", &n, &m) != EOF) {
Build(1, 1, n);
top = 0;
while(m--) {
scanf("%s", str);
if(str[0] == 'D') {
scanf("%d", &stack[top]);
Insert(1, stack[top], EK_BLACK);
top ++;
}else if(str[0] == 'R') {
if(top) {
top --;
Insert(1, stack[top], EK_WHITE);
}
}else {
scanf("%d", &x);
// 左連通、右連通
bool lc, rc;
printf("%d\n", Query(1, x, lc, rc));
}
}
}
return 0;
}
|