zoj2301Color the Ball(線段樹，離散化，成段更新)

題目鏈接：zoj2301

和poj2528做法基本一樣，建議先做poj的那道題

/*zoj2301Color the Ball 線段樹區間成段更新，離散化
題目大意：
    一些連續的球，編號從1~2^31-1，最初球都是黑色的
輸入塗色的區間和要塗的顏色，將區間內的球都塗色（端點處的球也塗色）
輸出連續的且都是白色球的最長的區間，相同的話輸出坐標小的
*/
#include
#include
#include
#include
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 4000;
bool hash[N<<3];
int col[N<<4];
int X[N<<2];
struct node
{
    int x,y,c;
    node(){}
    node(int a, int b, int cc):x(a),y(b),c(cc){}
}s[N<<2];
void pushdown(int rt)
{
    if(col[rt] != -1)
    {
        col[rt<<1] = col[rt<<1|1] = col[rt];
        col[rt] = -1;
    }
}
void update(int L, int R, int c, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        col[rt] = c;
        return;
    }
    pushdown(rt);
    int m = (l+r) >> 1;
    if(L <= m) update(L, R, c, lson);
    if(R > m) update(L, R, c, rson);
}
void query(int l, int r, int rt)
{
    if(col[rt] == 1)
    {
        for(int i = l; i <= r; i ++)
            hash[i] = true;
        return;
    }
    if(col[rt] == 0) return;
    int m = (l+r) >> 1;
    query(lson);
    query(rson);
}
int main()
{
    int i,n,j;
    while(~scanf("%d",&n))
    {
        char a[3];
        int x,y;
        memset(col, 0, sizeof(col));//0表示黑色
        memset(hash, false, sizeof(hash));
        int m = 0;
        for(i = 0; i < n; i ++)
        {
            scanf("%d%d%s",&x,&y,a);
            int c = a[0]=='b'?0:1;
            s[i] = node(x, y, c);
            X[m++] = x;
            X[m++] = y;
        }
        sort(X, X+m);
        int tot = 1;
        for(i = 1; i < m; i ++)
            if(X[i] != X[i-1]) X[tot++] = X[i];
        for(i = tot - 1; i > 0; i --)
            if(X[i] != X[i-1] + 1) X[tot++] = X[i-1] + 1;
        sort(X, X+tot);
        for(i = 0; i < n; i ++)
        {
            int l = lower_bound(X, X+tot, s[i].x) - X;
            int r = lower_bound(X, X+tot, s[i].y) - X;
            update(l+1, r+1, s[i].c, 1, tot, 1);
        }
        query(1, tot, 1);
        int ax,ay,alen = -1;
        for(i = 0; i <= tot; i ++)//查找長度最長且坐標最小的區間
        {
            if(hash[i])
            {
                for(j = i; j <= tot; j ++)
                    if(!hash[j]) break;
                if(X[j-2] - X[i-1] > alen)
                {
                    ax = X[i-1]; ay = X[j-2];
                    alen = ay - ax;
                }
                i = j - 1;
            }
        }
        printf("%d %d\n",ax,ay);
    }
    return 0;
}