POJ 2528 Mayors posters 線段樹（成段更新+離散化）

題意：
給出N個海報，每個海報有一個長度區間（a,b）.按順序貼在牆上。
問最後可以看到幾張海報。
思路：
一想到的就是線段樹，對每個區間進行染色，最後查找一共有多少種顏色。
第一次寫玩沒看數據大小。MLE了。。仔細一看，海報長度1QW。
然後寫了個離散化的，300MS+。
又去看了別人的離散化。。神多了。。60MS。。
優化後的離散
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string> 
#include <cmath> 
#include <cstring> 
#include <queue> 
#include <set> 
#include <vector> 
#include <stack> 
#include <map> 
#include <iomanip> 
#define PI acos(-1.0) 
#define Max 20005 
#define inf 1<<28 
#define LL(x) (x<<1) 
#define RR(x)(x<<1|1) 
using namespace std; 
 
struct kdq 
{ 
    int l,r,flag; 
} tree[Max*4]; 
 
struct kdq1 
{ 
    int num,id; 
} poster[Max]; 
 
int aa[Max][2]; 
void build_tree(int l,int r,int u) 
{ 
    tree[u].l=l; 
    tree[u].r=r; 
    tree[u].flag=0; 
    if(l==r)return ; 
    int mid=(l+r)>>1; 
    build_tree(l,mid,LL(u)); 
    build_tree(mid+1,r,RR(u)); 
} 
 
void update(int l,int r,int u,int i) 
{ 
    if(l>tree[u].r||r<tree[u].l)return ; 
    if(l==tree[u].l&&r==tree[u].r) 
    { 
        tree[u].flag=i; 
        return ; 
    } 
    if(tree[u].flag > 0 && tree[u].flag != i) 
    { 
        tree[LL(u)].flag = tree[u].flag; 
        tree[RR(u)].flag= tree[u].flag; 
        tree[u].flag = 0; 
    } 
    int mid=(tree[u].l+tree[u].r)>>1; 
    if(r<=mid) 
        update(l,r,LL(u),i); 
    else if(l>mid) 
        update(l,r,RR(u),i); 
    else 
    { 
        update(l,mid,LL(u),i); 
        update(mid+1,r,RR(u),i); 
    } 
    if(tree[LL(u)].flag==tree[RR(u)].flag) 
        tree[u].flag=tree[LL(u)].flag; 
    else 
        tree[u].flag=0; 
} 
 
int ans; 
bool visit1[20005]; 
 
void query(int l,int r,int u) 
{ 
    if(tree[u].flag&&!visit1[tree[u].flag]) 
        return ; 
    if(tree[u].flag) 
    { 
        ans+=visit1[tree[u].flag]; 
        visit1[tree[u].flag]=0; 
        return ; 
    } 
    int mid=(l+r)>>1; 
    query(l,mid,LL(u)); 
    query(mid+1,r,RR(u)); 
} 
bool cmp(kdq1 &a,kdq1 &b) 
{ 
    return a.num<b.num; 
} 
int main() 
{ 
    int i,j,k,l,n,m,T; 
    scanf("%d",&T); 
    int a,b; 
    while(T--) 
    { 
        memset(visit1,1,sizeof(visit1)); 
        scanf("%d",&n); 
        for(i=0; i<n; i++) 
        { 
            scanf("%d%d",&aa[i][0],&aa[i][1]); 
            poster[2*i].num=aa[i][0]; 
            poster[2*i].id=-(i+1); 
            poster[2*i+1].num=aa[i][1]; 
            poster[2*i+1].id=i+1; 
        } 
        sort(poster,poster+2*n,cmp); 
        int temp=poster[0].num; 
        int tp=1; 
        for(i=0; i<2*n; i++) 
        { 
            if(temp!=poster[i].num) 
            { 
                tp++; 
                temp=poster[i].num; 
            } 
            if(poster[i].id<0) 
            { 
                aa[-poster[i].id-1][0]=tp; 
            } 
            else 
            { 
                aa[poster[i].id-1][1]=tp; 
            } 
        } 
        build_tree(1,tp,1); 
        for(i=0; i<n; i++) 
            update(aa[i][0],aa[i][1],1,i+1); 
        ans=0; 
        query(1,tp,1); 
        printf("%d\n",ans); 
    } 
    return 0; 
} 
第一次寫的離散
[cpp]
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string> 
#include <cmath> 
#include <cstring> 
#include <queue> 
#include <set> 
#include <vector> 
#include <stack> 
#include <map> 
#include <iomanip> 
#define PI acos(-1.0) 
#define Max 20005 
#define inf 1<<28 
#define LL(x) (x<<1) 
#define RR(x)(x<<1|1) 
using namespace std; 
 
struct kdq 
{ 
    int l,r,flag; 
} tree[Max*4]; 
 
int aa[Max],bb[Max]; 
 
void build_tree(int l,int r,int u) 
{ 
    tree[u].l=l; 
    tree[u].r=r; 
    tree[u].flag=0; 
    if(l==r)return ; 
    int mid=(l+r)>>1; 
    build_tree(l,mid,LL(u)); 
    build_tree(mid+1,r,RR(u)); 
} 
 
void update(int l,int r,int u,int i) 
{ 
    if(l>tree[u].r||r<tree[u].l)return ; 
    if(l==tree[u].l&&r==tree[u].r) 
    { 
        tree[u].flag=i; 
        return ; 
    } 
    if(tree[u].flag > 0 && tree[u].flag != i) 
    { 
        tree[LL(u)].flag = tree[u].flag; 
        tree[RR(u)].flag= tree[u].flag; 
        tree[u].flag = 0; 
    } 
    int mid=(tree[u].l+tree[u].r)>>1; 
    if(r<=mid) 
        update(l,r,LL(u),i); 
    else if(l>mid) 
        update(l,r,RR(u),i); 
    else 
    { 
        update(l,mid,LL(u),i); 
        update(mid+1,r,RR(u),i); 
    } 
    if(tree[LL(u)].flag==tree[RR(u)].flag) 
        tree[u].flag=tree[LL(u)].flag; 
    else 
        tree[u].flag=0; 
} 
 
int ans; 
int yinshe[20005]; 
int visit[10000005]; 
bool visit1[20005]; 
 
void query(int l,int r,int u) 
{ 
    if(tree[u].flag&&!visit1[tree[u].flag]) 
        return ; 
    if(tree[u].flag) 
    { 
        ans+=visit1[tree[u].flag]; 
        visit1[tree[u].flag]=0; 
        return ; 
    } 
    int mid=(l+r)>>1; 
    query(l,mid,LL(u)); 
    query(mid+1,r,RR(u)); 
} 
 
int main() 
{ 
    int i,j,k,l,n,m,T; 
    scanf("%d",&T); 
    int a,b; 
    while(T--) 
    { 
        memset(visit1,1,sizeof(visit1)); 
        memset(visit,0,sizeof(visit)); 
        memset(yinshe,0,sizeof(yinshe)); 
        scanf("%d",&n); 
        int num=1; 
         for(i=1; i<=n; i++) 
         { 
             scanf("%d%d",&aa[i],&bb[i]); 
             if(!visit[aa[i]]) 
             { 
                 yinshe[num]=aa[i]; 
                 visit[aa[i]]=1; 
                 num++; 
             } 
             if(!visit[bb[i]]) 
             { 
                 yinshe[num]=bb[i]; 
                 visit[bb[i]]=1; 
                 num++; 
             } 
         } 
         sort(yinshe+1,yinshe+num); 
         for(i=1; i<num; i++) 
             visit[yinshe[i]]=i; 
         build_tree(1,num-1,1); 
        for(i=1;i<=n;i++) 
        update(visit[aa[i]],visit[bb[i]],1,i); 
        ans=0; 
        query(1,num-1,1); 
        printf("%d\n",ans); 
    } 
    return 0; 
}