POJ-2585-Mayor's posters-セグメント更新+(hash)離散化思想

テーマリンク:http://poj.org/problem?id=2528
このテーマはとても経典的な離散化段で線分樹の問題を更新します。何回も試してみて、十分に理解します。
回転:http://www.notonlysuccess.com/index.php/segment-tree-complete/
壁にポスターを貼ると、互いにカバーできます。最後に何枚かのポスターの構想が見られます。このデータは範囲が広いので、直接タイムアウト＋メモリを作ります。離散化が必要です。簡単に言えば、私達が必要な値だけを取って使います。例えば、区間[1000,2000]、[1990,2012]は使えません。したがって、私は1000,1990,2000,2012だけで十分です。それぞれ0,1,2,3に写像します。複雑さが大幅に下がります。だから離散化は必要な値を全部保存します。並べ替え後、それぞれ1~nに写像します。この複雑さは多くなくなります。この問題の難点は数字ごとに一つの単位の長さ（そして一つの点）を表しています。このような一般的な離散化は多くのエラーをもたらします。（私の以前のコードを含めて、pojというデータが珍しく弱いです。）次の二つの簡単な例は普通の離散化の欠陥を表しています。1-10-10-10-11-10-10-10このような欠陥を解決するために、順序付けされた配列にいくつかの処理を加えることができます。その中に任意の数字を加えて、例えば[1,2,3,6,7,10]を加えて、線分樹を作ればいいです。線分樹機能：udate:成段置換query:簡単hash
はい、今のコードはpojのデータしか過ぎません。本当に完璧ではありません。なぜかずっとREに来ています。教えてください。

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<cmath>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
//         10005,  RE，  ；
int pos[100005][2];  //       ，            ；
bool vis[100005];
int ans,mm;         //  ans        ，mm       ；
struct node1        //           ；
{
    int p,n;        //  p   ，n      ；
}Line[100005<<1];
struct node2        //        ；
{
    int l,r,c;
}node[100005<<2];
bool cmp(node1 x,node1 y)   //          ；
{
    return x.p<y.p;
}
void build(int l,int r,int rt)  //    ；
{
    node[rt].l=l;
    node[rt].r=r;
    node[rt].c=0;           //      ；
    if(l!=r){
        int mid=(l+r)>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
    }
}
void Insert(int l,int r,int c,int rt)   //    ；
{
    if(node[rt].l==l&&node[rt].r==r){
        node[rt].c=c;
        return;
    }
    if(node[rt].c>0&&node[rt].c!=c){    //            ，        PushDown;
        node[rt<<1].c=node[rt].c;
        node[rt<<1|1].c=node[rt].c;
        node[rt].c=0;
    }
    int mid=(node[rt].l+node[rt].r)>>1;
    if(r<=mid) Insert(l,r,c,rt<<1);
    else if(l>mid) Insert(l,r,c,rt<<1|1);
    else{
        Insert(l,mid,c,rt<<1);
        Insert(mid+1,r,c,rt<<1|1);
    }
}
void query(int rt)                  //      ；
{
    if(node[rt].c!=0){
        if(!vis[node[rt].c]){       //               ；
            ans++;
            vis[node[rt].c]=true;
        }
        return;
    }
    query(rt<<1);
    query(rt<<1|1);
}
int main()
{
    int t,n,a,b;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d%d",&a,&b);    //   a,b             
            Line[i<<1].p=a;
            Line[i<<1|1].p=b;
            Line[i<<1].n=-(i+1);    //          ；
            Line[i<<1|1].n=i+1;     //          ；
        }
        sort(Line,Line+2*n,cmp);    //    ；
        int temp=Line[0].p; mm=1;
        for(int i=0;i<2*n;i++){
            if(Line[i].p!=temp){
                mm++;
                temp=Line[i].p;
            }
            //if(i>0&&Line[i].p>(Line[i-1].p+1)) mm++;                 bug ，       RE，     POJ     ；
            if(Line[i].n<0) pos[-Line[i].n-1][0]=mm;
            else pos[Line[i].n-1][1]=mm;
        }
        build(1,mm,1);
        for(int i=0;i<n;i++){
            Insert(pos[i][0],pos[i][1],i+1,1);
        }
        memset(vis,false,sizeof(vis));
        ans=0;
        query(1);
        printf("%d
",ans);
    }
    return 0;
}