R. *【线段树】找最长“白色”线段[timus1019]

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

先是在数轴区间 $[0 ,10^9]$ 之间画上了白色。然后，这个区间的某一些部分又画上了黑色。然后某一些部分又画上白色，等等。请你找出经历 $M(1 \le M \le 5000)$ 次着色操作后，最长的白色区间。

首行位M,以下 $M$ 行着色的信息，每一行格式如下：

$a_i \ b_i c_i$ : 这里 $a_i,b_i$ 都是整数, $c_i$ 为字符 'b' 或 'w'，用空格隔开。

这三个参数描述：从 $a_i$ （点）到 $b_i$ （点）,着颜色c_i, ('w'表示白，'b'表示黑），可以认为 $0 < a_i \le b_i < 10^9$

输出两个整数 $x，y (x < y)$ ，之间用空格隔开，表示最长的白色区间。假如有多个答案，输出 $x# 最小的那个。

4
1 999999997 b
40 300 w
300 634 w
43 47 b

47 634