[离散化+线段树]poj2528

题意

      给出每个海报的位置，问最后没有被完全覆盖的海报有多少张

思路

      这里给的海报的端点值很大，需要离散化之后再用线段树求解。离散化写挫被坑了好多发，注意这三组数据。

3

3

3 4

1 3

4 10

//答案是2

 

3

1 5

1 3

4 5

//答案是2

 

3

1 10

1 3

6 10

//答案是3

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int nMax = 100000;
struct{
    int l,r,val;  //-1杂色  0无色  1---k纯色
}node[nMax * 3];

struct{
    int a,b;
}ad[nMax];
int num[4*nMax];
int hash[10000010];
void build(int l ,int r ,int u){
    node[u].l = l;
    node[u].r = r;
    node[u].val = 0;
    if(l == r)return;
    int m = (l + r)>>1;
    build(l ,m ,u*2);
    build(m+1 ,r ,u*2+1);
}

void update(int left ,int right ,int val ,int u){
    if(left == node[u].l && right == node[u].r){
//    cout<<left <<" "<<right <<" "<<u<<endl;
        node[u].val = val;
        return;
    }
    if(node[u].val != -1){
        node[u*2].val = node[u*2+1] .val = node[u].val;
        node[u].val = -1;
    }
    int m = (node[u].l + node[u].r)>>1;
    if(right <= m){
        update(left ,right ,val ,u*2);
        return;
    }
    if(left >= m+1){
        update(left ,right ,val ,u*2+1);
        return;
    }
    update(left ,m ,val ,u*2);
    update(m+1 ,right ,val ,u*2+1);
}

void query(int left ,int right ,int u){
//    cout<<left <<" e e "<<right<<endl;
    if(node[u].val != -1){
//            cout<<"get\n";
        num[node[u].val] = 1;
        return;
    }
    int m =(node[u].l + node[u].r)>>1;
    if(left <= m){
       query(left ,min(m ,right) ,u*2);
    }
    if(right >= m+1){
        query(max(m+1 ,left) ,right ,u*2 + 1);
    }
}
int main(){
    int tcs ,n ,i ,k;
    scanf("%d",&tcs);
    while(tcs--){
        scanf("%d",&n);
        k = 0;
        for(i = 1 ;i <= n ;i++){
            scanf("%d%d",&ad[i].a,&ad[i].b);
            num[k++] = ad[i].a;
            num[k++] = ad[i].b;
        }
        sort(num ,num + k);
        memset(hash,0,sizeof(hash));
        int tmp = 0;
        hash[num[0]] = 1;
        int nk = 2;
        for(i=1 ;i < k ;i++){
            if(num[i] - num[i-1] > 1)tmp++;
            if(!hash[num[i]]){
                    hash[num[i]] = nk + tmp;
                    nk++;
            }
//            if(num[i]!=num[i-1])hash[num[i]] = (i + 1) + tmp;
        }
        for(i = 1 ;i <= n ;i++){
            ad[i].a = hash[ad[i].a];
            ad[i].b = hash[ad[i].b];
        }
        build(1 ,nk + tmp,1);
//        cout<<" -------------\n";
        for(i = 1 ;i <= n;i++){
//            cout<<ad[i].a<<" "<<ad[i].b<<endl;
            update(ad[i].a ,ad[i].b ,i ,1);
//            cout<<endl<<endl;
        }
        memset(num ,0 ,sizeof(num));
        int ans = 0;
        query(1 ,nk + tmp,1);
        for(i = 1 ;i <= n ;i++){
            if(num[i])ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}