|
|
題目鏈接：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)，問染色完畢后最長的白色序列。
解法：
線段樹+離散化
思路：
線段樹染色問題，我的做法比較麻煩，如果直接用離散化會(huì)簡單許多
，但是這題是練習(xí)線段樹的好題，它同樣涉及到了lazy思想。因?yàn)橐蟮?br>區(qū)間內(nèi)最長的白色序列，線段樹的字段里面必須保存和這個(gè)長度有關(guān)的信
息，我的域如下：
int Color; // 當(dāng)前區(qū)間的顏色
int lMax; // 包含左區(qū)間的連續(xù)白色的最大值時(shí)的最右端點(diǎn)
int rMax; // 包含右區(qū)間的連續(xù)白色的最大值時(shí)的最左端點(diǎn)
int MaxLR[2]; // 當(dāng)前結(jié)點(diǎn)管轄區(qū)間的最優(yōu)值的區(qū)間
int l, r; // 當(dāng)前結(jié)點(diǎn)管理的左右區(qū)間
我們用以下函數(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ò)，Color字段其實(shí)是
充當(dāng)了lazy標(biāo)記的作用，用于染色的時(shí)候?qū)⑺鼘＿f到子樹。
[l, lMax]組成了當(dāng)前結(jié)點(diǎn)的包含左閉區(qū)間的最優(yōu)解。
[rMax, r]組成了當(dāng)前結(jié)點(diǎn)的包含右閉區(qū)間的最優(yōu)解。
[MaxLR[0], MaxLR[1]] 則是當(dāng)前區(qū)間的最優(yōu)解。
這樣我們就可以通過傳遞性在兒子結(jié)點(diǎn)的屬性都得知的情況下將父親的值
計(jì)算出來，最后遞歸到根結(jié)點(diǎn)。具體的計(jì)算過程可以自己畫棵樹看一下，
在計(jì)算MaxLR的時(shí)候稍微麻煩一點(diǎn)。
 */
#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; // 當(dāng)前區(qū)間的顏色
int lMax; // 包含左區(qū)間的連續(xù)白色的最大值時(shí)的最右端點(diǎn)
int rMax; // 包含右區(qū)間的連續(xù)白色的最大值時(shí)的最左端點(diǎn)
int MaxLR[2]; // 當(dāng)前結(jié)點(diǎn)管轄區(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
*/
|