题目大意;说是可以吧一段区间变成白色或者黑色， 区间（0-10^9）初始都是白色，问经过n次操作以后最大的连续白色区间

Problem Description

The segment of numerical axis from 0 to 10

⁹ is painted into white color. After that some parts of this segment are painted into black, then some into white again and so on. In total there have been made 

N re-paintings (1 ≤ 

N ≤ 5000). You are to write a program that finds the longest white open interval after this sequence of re-paintings.

 

Input

The first line of input contains the only number 

N. Next 

N lines contain information about re-paintings. Each of these lines has a form:

a_i b_i c_i

where 

a_i and 

b_i are integers, 

c_i is symbol 'b' or 'w', 

a_i, 

b_i, 

c_i are separated by spaces. 

This triple of parameters represents repainting of segment from 

a_i to 

b_i into color 

c_i ('w' white, 'b' black). You may assume that 0 < 

a_i < 

b_i < 10

⁹.

 

Output

Output should contain two numbers 

x and 

y (

x < 

y) divided by space(s). These numbers should define the longest white open interval. If there are more than one such an interval output should contain the one with the smallest 

x.

 

Sample Input

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

 

 

#include<iostream>

#include<algorithm>

#include<cstdio>

using namespace std;

#define maxn 5000

struct node

{

    int L, R, color;

    int Mid(){return (L+R)/2;}

};

node a[maxn*4*2];

int point[maxn*2+10], npoint;

int maxv, minv, First, Last, color;

void BuildTree(int r, int L, int R);

void Insert(int r, int L, int R, int color);

void Query(int r);

int main()

{

    int N;

    while(scanf("%d", &N) != EOF)

    {

        int i, L[maxn+10], R[maxn+10], c[maxn+10];

        char ch;

        for(npoint=i=0; i<N; i++)

        {

            cin >> L[i] >> R[i] >> ch;

            c[i] = (ch == 'w' ? 0 : 1);

            point[npoint++] = L[i];

            point[npoint++] = R[i];

        }

        point[npoint++] = 0, point[npoint++] = 1000000000;

        sort(point, point+npoint);

        npoint = unique(point, point+npoint) - point;

        BuildTree(1, 0, npoint-1);

        for(i=0; i<N; i++)

        {

            L[i] = lower_bound(point, point+npoint, L[i]) - point;

            R[i] = lower_bound(point, point+npoint, R[i]) - point;

            Insert(1, L[i], R[i], c[i]);

        }

        maxv = minv = First = Last = 0;

        color = 0;

        Query(1);

        printf("%d %d\n", minv, maxv);

    }

    return 0;

}

void BuildTree(int r, int L, int R)

{

    a[r].L = L, a[r].R = R, a[r].color = 0;

    if(R - L == 1)return ;

    BuildTree(r*2, L, a[r].Mid());

    BuildTree(r*2+1, a[r].Mid(), R);

}

void Insert(int r, int L, int R, int C)

{

    if(a[r].color == C)return ;

    if(a[r].L == L && a[r].R == R)

    {

        a[r].color = C;

        return ;

    }

    if(a[r].color >= 0)

        a[r*2].color = a[r*2+1].color = a[r].color;

    a[r].color = -1;

    if(R <= a[r].Mid())

        Insert(r*2, L, R, C);

    else if(L >= a[r].Mid())

        Insert(r*2+1, L, R, C);

    else

    {

        Insert(r*2, L, a[r].Mid(), C);

        Insert(r*2+1, a[r].Mid(), R, C);

    }

}

void Query(int r)

{

    if(a[r].color == 0)

    {

        Last = a[r].R;

        if(color == 1)

        {

            color = a[r].color;

            First = a[r].L;

        }

        if(maxv-minv < point[Last] - point[First])

                maxv = point[Last], minv = point[First];

        return ;

    }

    if(a[r].color == 1)

    {

        color = 1;

        return ;

    }

    Query(r*2);

    Query(r*2+1);

}