POJ 2528 Mayor's posters(hash+セグメントツリーセグメント更新)

壁があり、1 QW部に等分され、1部の幅は1単位の幅である.今壁にN枚のポスターを貼って、1枚のポスターの幅は任意で、しかし必ず単位の幅の整数倍で、しかも<=1 QW.後付けのポスターが先付けのポスターと交わると、後付けのポスターは必ず先付けのポスターを全部または一部覆う.各ポスターに貼られている位置(左端位置と右端位置)を示し、N枚のポスターを貼った後、何枚のポスターが見えますか?(PS:一部を見ても見えます.)
構想:簡単なセグメント更新ですが、データ量は1千万で、MTになるので、区間圧縮(離散化)し、カバーの関係が変わらないことを保証します.離散化の時に間違いやすい細部があります.pojデータ水、この間違いやすい点はhh牛の話を引用します.
この問題の難点は、各数字が実際に1つの単位長(1つの点ではない)を表していることであり、このような一般的な離散化は多くの誤り(私の以前のコード、pojという問題のデータが非常に弱いことを含む)をもたらし、以下の2つの簡単な例は一般的な離散化の欠陥を体現することができるはずである.例1:1-10 1-45-10例2:1-10一般的な離散化後、すべて[1,4][1,2][3,4]セグメント2が[1,2]をカバーし、セグメント3が[3,4]をカバーし、では、線分1は完全に覆われていますか?例1は完全に覆われているが,例2は覆われていない.

//1412 KB 79 ms
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define M 10005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int col[M*16];
int poi[M*4]; // ， 2*M 
int li[M],ri[M];
bool book[M];
void build(int l,int r,int rt)
{
    col[rt]=-1;
    if(l==r) return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
int Bin(int g,int m)  // 
{
    int l=0,r=m-1;
    while(r>=l){
        int mid=(l+r)>>1;
        if(poi[mid]==g) return mid;
        else if(poi[mid]>g) r=mid-1;
        else l=mid+1;
    }
}
void pushdown(int rt)
{
    if(col[rt]==-1) return ;
    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);
}
int query(int l,int r,int rt)
{
    int ans=0;
    if(col[rt]!=-1){
       if(!book[col[rt]]){
            book[col[rt] ]=true;
            ans++;
       }
       return ans;
    }
    if (l == r) return 0;
    int m=(l+r)>>1;
    ans+=query(lson);
    ans+=query(rson);
    return ans;
}
int main()
{
    int cas,n;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d",&n);
        int cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&li[i],&ri[i]);
            poi[cnt++]=li[i];
            poi[cnt++]=ri[i];
        }
        sort(poi,poi+cnt);
        int top=1;
        for(int i=1;i<cnt;i++){
            if(poi[i]!=poi[i-1]){ // 
                poi[top++]=poi[i];
            }

        }
        int tmp=top;

        for(int i=1;i<tmp;i++){ // 
            if(poi[i]-poi[i-1]>1){
                poi[top++]=poi[i-1]+1;
            }
        }
        sort(poi,poi+top);

        build(0,top-1,1);
        int c=0; // 

        for(int i=1;i<=n;i++){

            int l=Bin(li[i],top);
            int r=Bin(ri[i],top);
            update(l,r,++c,0,top-1,1);

        }
        memset(book,0,sizeof(book));

        printf("%d
",query(0,top-1,1));
    }
    return 0;
}