ZOJ 3518 Unisafe Factor(区間カバー:離散化)

ZOJ 3518 Unisafe Factor(区間カバー:離散化)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3518
件名:
       あなたに[0,L]の初期の区間をあげて、順番にn 1+n 2の区間をあげます.毎回、一つの区間内の全ての整点位置の値+1をさせます.最終的な連続値1の区間は一番長いのはいくらですか?
分析:
       典型的な離散化問題(線分樹を使うともっと理解できそうです.)離散化問題の一番重要なところはどうやって元問題の大きな区間を一つのサブ区間に転化しますか?   また、任意のサブ区間は重複しておらず、元の大区間はいずれも特定の複数のサブ区間で構成されています.
       現在入力区間が[1,3]と[2,5]があれば、簡単にサブ区間を[1,2]、[2,3]と[3,5]に分けることができますか?いいえ、2と3は1つの点(1区間)を表していますので、［1,2］と［2,3］は重複部分があります.だからここで考え方を変えます.
私たちはまず入力区間を［1,4］と［2,6］(半閉半開き区間)に変更します.すると、サブ区間は入力区間のx 1とx 2の値から［1,2］［2,4］［4,6］に並べられ、ちょうど3段の重複しないサブ区間であり、元の入力区間を完全にカバーしています.
       上の部分をやり終えたら、私達はただ元の区間を遍歴して、例えば[1,4]して、この区間でカバーできるサブエリア間の首座標の下付き座標を探し出して(ここは0と2)、そして0と1サブ区間(2サブ区間を含まない)に対して上書き操作をすればいいです.
       最終的には最長の連続値が1の区間を直接求められます.
ACコード:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400000+10;

struct Node//  
{
    int x1,x2;
}nodes[maxn];

int n;      //    
int x[maxn];//x  
int num;    //x    

int main()
{
    int L,n1,n2;
    while(scanf("%d%d%d",&L,&n1,&n2)==3)
    {
        n=n1+n2;
        num=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d%d",&nodes[i].x1,&nodes[i].x2);
            ++nodes[i].x2;
            x[num++]=nodes[i].x1;
            x[num++]=nodes[i].x2;
        }
        sort(x,x+num);
        num=unique(x,x+num)-x;

        bool mp[maxn];//       
        memset(mp,0,sizeof(mp));
        for(int i=0;i<n;++i)
        {
            int L_x=lower_bound(x,x+num,nodes[i].x1)-x;
            int R_x=lower_bound(x,x+num,nodes[i].x2)-x;

            for(int j=L_x;j<R_x;++j)
                mp[j] ^= true;
        }
        int sum=0;
        for(int i=0;i<num-1;++i)if(mp[i])
        {
            int cur=0;
            while(i<num-1 && mp[i])
            {
                cur+= x[i+1]-x[i];
                ++i;
            }
            sum=max(sum,cur);
        }
        printf("%d
",sum);
    }
    return 0;
}