题意:在区间[0, 10^9]上染黑白两种颜色,问最后最长的白段的起点和终点。(初始区间全白)
题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1019
——>>看数据可知要离散化。。而题意可知可用线段树去解决。。
对于区间[x, y],因为点到点,不是段到段,所以,可让x表示[x, x+1],整个区间的最后一点不表示,转化成段到段来解决。。于是[x, y]转化为[x, y-1]。。
时间复杂度为O(n)
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define lc (o<<1) #define rc ((o<<1)|1) const int maxn = 5000 + 10; char cover[maxn<<3], color[maxn<<3]; //结点数已<<1,线段树结点再<<2,总<<3 int N, a[maxn], b[maxn], buf[maxn<<1], cnt; char c[maxn]; void read() { cnt = 0; buf[++cnt] = 0; buf[++cnt] = 1000000000; for(int i = 1; i <= N; i++) { scanf("%d%d %c", a+i, b+i, c+i); buf[++cnt] = a[i]; buf[++cnt] = b[i]; } } void discretize() { sort(buf + 1, buf + 1 + cnt); cnt = unique(buf + 1, buf + 1 + cnt) - buf - 1; //求个数要-1 } void build(int o, int L, int R) { cover[o] = 0; if(L == R) return; int M = (L + R) >> 1; build(lc, L, M); build(rc, M + 1, R); } void pushdown(int o) { if(cover[o]) { cover[lc] = cover[rc] = cover[o]; cover[o] = 0; } } void Insert(int o, int L, int R, int ql, int qr, char color) { if(ql <= L && R <= qr) { cover[o] = color; return; } pushdown(o); int M = (L + R) >> 1; if(ql <= M) Insert(lc, L, M, ql, qr, color); if(qr > M) Insert(rc, M+1, R, ql, qr, color); } void query(int o, int L, int R, int ql, int qr) { if(cover[o]) { //我这个才正点! for(int i = L; i <= R; i++) color[i] = cover[o]; return; } if(L == R) { color[L] = cover[o]; if(color[L] == 0) color[L] = 'w'; //还是判一下 return; } pushdown(o); int M = (L + R) >> 1; if(ql <= M) query(lc, L, M, ql, qr); if(qr > M) query(rc, M+1, R, ql, qr); } void solve() { for(int i = 1; i <= N; i++) { int A = lower_bound(buf + 1, buf + 1 + cnt, a[i]) - buf; int B = lower_bound(buf + 1, buf + 1 + cnt, b[i]) - buf; Insert(1, 1, cnt, A, B-1, c[i]); //cnt个点,cnt-1段 } query(1, 1, cnt, 1, cnt-1); //只查cnt-1段 int L = 0, R = 0, Max = 0; for(int i = 1; i < cnt; i++) { if(color[i] == 'w') { int l = i; while(i < cnt && color[i] == 'w') i++; int r = i; if(buf[r] - buf[l] > Max) { L = buf[l]; R = buf[r]; Max = R - L; } } } printf("%d %d\n", L, R); } int main() { while(scanf("%d", &N) == 1) { read(); discretize(); build(1, 1, cnt); solve(); } return 0; }