|
|
題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2301
  /**//*
 題意：
給出N(N <= 2000)組操作，每組操作的形式如下：
A B C: 將[A,B]區(qū)間內(nèi)的顏色染成C，C可以是白色或者黑色，序列開始
是全黑色的，并且范圍在int范圍內(nèi)，問染色完畢后最長的白色序列。
解法：
線段樹+離散化
思路：
線段樹染色問題，我的做法比較麻煩，如果直接用離散化會簡單許多
，但是這題是練習線段樹的好題，它同樣涉及到了lazy思想。因為要求得
區(qū)間內(nèi)最長的白色序列，線段樹的字段里面必須保存和這個長度有關的信
息，我的域如下：
int Color; // 當前區(qū)間的顏色
int lMax; // 包含左區(qū)間的連續(xù)白色的最大值時的最右端點
int rMax; // 包含右區(qū)間的連續(xù)白色的最大值時的最左端點
int MaxLR[2]; // 當前結點管轄區(qū)間的最優(yōu)值的區(qū)間
int l, r; // 當前結點管理的左右區(qū)間
我們用以下函數(shù)從左右兒子中得到當前結點的信息：
void UpdateBy(Tree* ls, Tree* rs);
之所以把它寫成函數(shù)是因為這里的處理比較麻煩，很容易出錯，并且需要
調(diào)用多次，這個函數(shù)的作用就是通過左右兒子的信息填充本身的信息。
信息一多，處理的時候就要極為小心，因為很容易出錯，Color字段其實是
充當了lazy標記的作用，用于染色的時候將它專遞到子樹。
[l, lMax]組成了當前結點的包含左閉區(qū)間的最優(yōu)解。
[rMax, r]組成了當前結點的包含右閉區(qū)間的最優(yōu)解。
[MaxLR[0], MaxLR[1]] 則是當前區(qū)間的最優(yōu)解。
這樣我們就可以通過傳遞性在兒子結點的屬性都得知的情況下將父親的值
計算出來，最后遞歸到根結點。具體的計算過程可以自己畫棵樹看一下，
在計算MaxLR的時候稍微麻煩一點。
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
#define MUTIPLE_COLOR -1
#define BLACK 0
#define WHITE 1
#define maxn 8200
#define ul unsigned int
struct point  {
int l, r;
char color;
  point() {}
point(int _l, int _r, char _c) {
l = _l;
r = _r;
color = _c;
 }
};
vector <point> pt;
int n;
ul tmp[maxn], tmpsize;
ul bin[maxn], size;
void Process() {
sort(tmp, tmp + tmpsize);
bin[ size = 1 ] = tmp[0];
for(int i = 1; i < tmpsize; i++) {
if(tmp[i] != tmp[i-1])
bin[ ++size ] = tmp[i];
}
}
int Binary(int v) {
int l = 1;
int r = size;
while(l <= r) {
int m = (l + r) >> 1;
if(bin[m] == v)
return m;
if(v > bin[m])
l = m + 1;
else
r = m - 1;
}
}
struct Tree {
int Color; // 當前區(qū)間的顏色
int lMax; // 包含左區(qū)間的連續(xù)白色的最大值時的最右端點
int rMax; // 包含右區(qū)間的連續(xù)白色的最大值時的最左端點
int MaxLR[2]; // 當前結點管轄區(qū)間的最優(yōu)值的區(qū)間
int l, r;
int son[2];
char lVal, rVal;
void clear() {
son[0] = son[1] = -1;
AssignColor(BLACK);
}
int len() {
return r - l + 1;
}
void AssignColor(int nColor);
void TranslateToSon();
void WhiteProcess();
void BlackProcess();
void UpdateBy(Tree* ls, Tree* rs);
void MaxVal(int xl, int xr);
}T[maxn*3];
int root, tot;
int MMax(int a, int b) {
return a > b ? a : b;
}
int GetID(int& root, int l, int r) {
if(root == -1) {
root = tot++;
T[root].l = l;
T[root].r = r;
T[root].clear();
}
return root;
}
void Tree::WhiteProcess() {
lMax = r;
rMax = l;
MaxLR[0] = l;
MaxLR[1] = r;
}
void Tree::BlackProcess() {
lMax = l - 1;
rMax = r + 1;
MaxLR[0] = -1;
MaxLR[1] = -1;
}
void Tree::AssignColor(int nColor) {
Color = nColor;
if(nColor == MUTIPLE_COLOR)
return ;
if(Color == WHITE) {
WhiteProcess();
}else if(Color == BLACK){
BlackProcess();
}
lVal = rVal = Color;
}
void Tree::TranslateToSon() {
if(Color != MUTIPLE_COLOR) {
int mid = (l + r) >> 1;
int i0 = GetID(son[0], l, mid);
T[i0].AssignColor(Color);
int i1 = GetID(son[1], mid+1, r);
T[i1].AssignColor(Color);
Color = MUTIPLE_COLOR;
}
}
void Tree::MaxVal(int xl, int xr) {
if(xl != -1 && xl <= xr) {
bool con = (MaxLR[0] == -1)
|| (bin[xr] - bin[xl] > bin[ MaxLR[1] ] - bin[ MaxLR[0] ])
|| (bin[xr] - bin[xl] == bin[ MaxLR[1] ] - bin[ MaxLR[0] ] && bin[xl] < bin[MaxLR[0]]);
if(con) {
MaxLR[0] = xl;
MaxLR[1] = xr;
}
}
}
void Tree::UpdateBy(Tree* ls, Tree* rs) {
lVal = ls->lVal;
rVal = rs->rVal;
lMax = (ls->lMax==ls->r) ? rs->lMax : ls->lMax;
rMax = (rs->rMax==rs->l) ? ls->rMax : rs->rMax;
if(ls->Color == rs->Color) {
Color = ls->Color;
}else
Color = MUTIPLE_COLOR;
MaxLR[0] = MaxLR[1] = -1;
MaxVal(l, lMax);
MaxVal(rMax, r);
MaxVal(ls->rMax, rs->lMax);
MaxVal(ls->MaxLR[0], ls->MaxLR[1]);
MaxVal(rs->MaxLR[0], rs->MaxLR[1]);
}
void Insert(int& root, int nl, int nr, int l, int r, int val) {
if(nl > r || nr < l)
return ;
GetID(root, l, r);
if(T[root].Color == val)
return ;
if(nl <= l && r <= nr) {
T[root].AssignColor(val);
return ;
}
T[root].TranslateToSon();
int mid = (l + r) >> 1;
Insert(T[root].son[0], nl, nr, l, mid, val);
Insert(T[root].son[1], nl, nr, mid + 1, r, val);
T[root].UpdateBy(&T[ T[root].son[0] ], &T[ T[root].son[1] ]);
}
int main() {
int i;
int a, b;
char str[10];
while(scanf("%d", &n) != EOF) {
tmpsize = 0;
pt.clear();
for(i = 0; i < n; i++) {
scanf("%d %d %s", &a, &b, str);
tmp[ tmpsize++ ] = a - 1;
tmp[ tmpsize++ ] = a;
tmp[ tmpsize++ ] = b;
tmp[ tmpsize++ ] = (ul)b + 1;
pt.push_back(point(a, b, str[0]=='w' ? WHITE : BLACK));
}
Process();
root = -1;
tot = 0;
Insert(root, 1, size, 1, size, BLACK);
for(i = 0; i < n; i++) {
int l = Binary(pt[i].l);
int r = Binary(pt[i].r);
Insert(root, l, r, 1, size, pt[i].color);
}
if(T[root].MaxLR[0] == -1)
printf("Oh, my god\n");
else {
printf("%d %d\n", bin[ T[root].MaxLR[0] ], bin[ T[root].MaxLR[1] ]);
}
}
return 0;
}
/**//*
3
1 100000 w
2 6 b
100 1000 b
*/
|