hdu 1199 Color the Ball(離散化線段樹)

Color the Ball
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3529    Accepted Submission(s): 874

Problem Description
There are infinite balls in a line (numbered 1 2 3 ....), and initially all of them are paint black. Now Jim use a brush paint the balls, every time give two integers a b and follow by a char 'w' or 'b', 'w' denotes the ball from a to b are painted white, 'b' denotes that be painted black. You are ask to find the longest white ball sequence.

Input
First line is an integer N (<=2000), the times Jim paint, next N line contain a b c, c can be 'w' and 'b'.

There are multiple cases, process to the end of file.

Output
Two integers the left end of the longest white ball sequence and the right end of longest white ball sequence (If more than one output the small number one). All the input are less than 2^31-1. If no such sequence exists, output "Oh, my god".

Sample Input
3
1 4 w
8 11 w
3 5 b

Sample Output
8 11 

//好事惡習啊，我都快要吐了，第一次做離散化的線段樹
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 4040
int a[N],r[N],p[N],c[N],f[N];//r[i]排名i的原位置，p[i]原位置i的排名
int cmp(int i,int j){
    return a[i]<a[j];
}
struct node{
    int l,r,lz;
    void init(int _l,int _r){
        l=_l;r=_r;lz=-1;
    }
}t[4*N];
void build(int l,int r,int k){
    if(l>=r)return;
    t[k].init(l,r);
    if(l+1>=r)return;
    int md=(l+r)/2;
    build(l,md,k*2);
    build(md,r,k*2+1);//不是md+1(因為md被覆蓋)
}
void down(int k){
	if(t[k].l+1==t[k].r)return;
    if(t[k].lz==-1)return;
    t[k*2].lz=t[k*2+1].lz=t[k].lz;
    t[k].lz=-1;
}
void DownAll(int k){
    if(t[k].lz!=-1){
        for(int i=t[k].l;i<t[k].r;i++)f[i]=t[k].lz;//右端點不標記(只有被覆蓋時才標記)
        return ;
    }
    DownAll(k*2);
    DownAll(k*2+1);
}
void update(int l,int r,int cr,int k){
    if(t[k].l>=t[k].r)return;
    if(l==t[k].l&&r==t[k].r){
        t[k].lz=cr;//標記
        return;
    }
    down(k);
    if(t[k].l+1>=t[k].r)return;

    int md=(t[k].l+t[k].r)/2;
    if(md>=r)update(l,r,cr,k*2);
    else if(l>md)update(l,r,cr,k*2+1);
    else{
        update(l,md,cr,k*2);
        update(md,r,cr,k*2+1);
    }
}
int main(){
    int i,j,k,n;
    int x,y;
	char ch;
    while(~scanf("%d",&n)){
        for(i=j=0;i<n;i++){
            scanf("%d%d %c",&x,&y,&ch);
			c[i]=(ch=='w');
            //l-1 或r+1 [)一閉一開離散化
            r[j]=j;a[j]=x;++j;
            r[j]=j;a[j]=y+1;++j;
        }
        
        sort(r,r+j,cmp);
        //去重
        p[r[0]]=k=0;//第0位的a，排第0位
        for(i=1;i<j;i++){
            if(a[r[i]]!=a[r[i-1]])a[r[++k]]=a[r[i]];
            p[r[i]]=k;
        }
        //for(i=0;i<j;i++)cout<<p[r[i]]<<" ";cout<<endl;
        //初始化樹
        build(0,k,1);
        memset(f,0,sizeof(f));//0黑色1白色
        //update
        for(i=0,n+=n;i<n;i+=2){
            x=p[i];
            y=p[i+1];
            update(x,y,c[i/2],1);//區間更新
        }
        DownAll(1);
       // for(i=0;i<=k;i++)cout<<f[i]<<" ";cout<<endl;
        int tx,ty;
        for(i=x=y=0;i<=k;i++){
            if(f[i]==0)continue;
            tx=a[r[i]];
            while(f[i]==1)i++;
            ty=a[r[i]];
            if(ty-tx>y-x){x=tx;y=ty;}
        }
        if(x==y) puts("Oh, my god");
        else printf("%d %d\n",x, y-1);

    }
return 0;
}