可以用线段树进行区间染色、合并的操作。
由于数据范围比较小，离散化后直接暴力更新也是可以的。
#include#include #include #define MAXD 10010int N, lc[4 * MAXD], rc[4 * MAXD], mc[4 * MAXD], to[4 * MAXD];int M, tx[MAXD];struct Seg{ int x, y; char b[5]; }seg[MAXD];int cmp(const void *_p, const void *_q){ int *p = (int *)_p, *q = (int *)_q; return *p < *q ? -1 : 1; }void build(int cur, int x, int y){ int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; lc[cur] = rc[cur] = mc[cur] = tx[y + 1] - tx[x]; to[cur] = -1; if(x == y) return ; build(ls, x, mid); build(rs, mid + 1, y); }void init(){ int i, j, k; for(i = 0; i < N; i ++) { scanf("%d%d%s", &seg[i].x, &seg[i].y, seg[i].b); tx[i << 1] = seg[i].x, tx[(i << 1) | 1] = seg[i].y; } tx[i << 1] = 0, tx[(i << 1) | 1] = 1000000000; qsort(tx, (N + 1) << 1, sizeof(tx[0]), cmp); M = 0; for(i = 1; i < ((N + 1) << 1); i ++) if(tx[i] != tx[i - 1]) tx[++ M] = tx[i]; build(1, 0, M - 1);}void pushdown(int cur, int x, int y){ int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(to[cur] != -1) { to[ls] = to[rs] = to[cur]; mc[ls] = lc[ls] = rc[ls] = (to[cur] ? 0 : tx[mid + 1] - tx[x]); mc[rs] = lc[rs] = rc[rs] = (to[cur] ? 0 : tx[y + 1] - tx[mid + 1]); to[cur] = -1; } }int Max(int x, int y){ return x > y ? x : y; }void update(int cur, int x, int y){ int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; mc[cur] = Max(mc[ls], mc[rs]); mc[cur] = Max(mc[cur], rc[ls] + lc[rs]); lc[cur] = lc[ls] + (lc[ls] == tx[mid + 1] - tx[x] ? lc[rs] : 0); rc[cur] = rc[rs] + (rc[rs] == tx[y + 1] - tx[mid + 1] ? rc[ls] : 0);}int BS(int x){ int mid, min = 0, max = M + 1; for(;;) { mid = (min + max) >> 1; if(mid == min) break; if(tx[mid] <= x) min = mid; else max = mid; } return mid;}void color(int cur, int x, int y, int s, int t, int c){ int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x >= s && y <= t) { to[cur] = c; mc[cur] = lc[cur] = rc[cur] = (c ? 0 : tx[y + 1] - tx[x]); return ; } pushdown(cur, x, y); if(mid >= s) color(ls, x, mid, s, t, c); if(mid + 1 <= t) color(rs, mid + 1, y, s, t, c); update(cur, x, y);}void Search(int cur, int x, int y, int &s, int &t){ int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1; if(x == y) { s = tx[x], t = tx[y + 1]; return ; } pushdown(cur, x, y); if(mc[ls] == mc[cur]) Search(ls, x, mid, s, t); else if(rc[ls] + lc[rs] == mc[cur]) s = tx[mid + 1] - rc[ls], t = tx[mid + 1] + lc[rs]; else Search(rs, mid + 1, y, s, t);}void solve(){ int i, j, k; for(i = 0; i < N; i ++) { j = BS(seg[i].x), k = BS(seg[i].y); if(j < k) { if(seg[i].b[0] == 'b') color(1, 0, M - 1, j, k - 1, 1); else color(1, 0, M - 1, j, k - 1, 0); } } Search(1, 0, M - 1, j, k); printf("%d %d\n", j, k);}int main(){ while(scanf("%d", &N) == 1) { init(); solve(); } return 0; }