Problem1103--线段树5(找最长线段(体会离散化和线段树的细节))

1103: 线段树5(找最长线段(体会离散化和线段树的细节))

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 1  Solved: 1
[Status] [Submit] [Creator:]

Description

【题目描述】
        先是在数轴区间 0 到10^9 (10的9次方)之间画上了白色。然后,这个区间的某一些部分又画上了黑色。然后某一些部分又画上白色,等等。请你找出经历M(1 <= M <= 5000)次着色操作后,最长的白色区间。
【输入格式】
        首行位M,以下M行位重着色的信息,每一行格式如下:
        ai bi ci 这里 ai ,bi 都是整数, ci 为字符'b' 或'w',用空格隔开。
        这三个参数描述:从ai到bi,着颜色ci, ('w'表示白,'b'表示黑),可以认为0 < ai <= bi < 10^9
【输出格式】
        输出x,y (x < y),之间用空格隔开,表示最长的白色区间。假如有多个答案,输出x最小的那个 
【样例输入】
4
1 999999997 b
40 300 w
300 634 w
43 47 b
【样例输出】
47 634

这道题:线段树+离散化

Source/Category