poj 2528 Mayor's posters

点击打开链接poj2528

思路：离散化+线段树成段更新
分析：
1 首先这一题的数据是错误的，这题的区间的最大值为10000000，如果我们按照正常的线段树的思路去做的话肯定是会超内存和超时的。
2 所以我们应该考虑离散化，我们把区间离散成集中的区间。但是这个地方会有个问题
给出下面两个简单的例子应该能体现普通离散化的缺陷:
例子一:1-10 1-4 5-10
例子二:1-10 1-4 6-10
普通离散化后都变成了[1,4][1,2][3,4]
线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.

代码：

#include<set>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 10010;
struct Node{
    int left;
    int right;
    int mark;
};
Node node[4*MAXN] , tmp[MAXN];
int n , pos;
int num[2*MAXN];
set<int>s;

void hash_map(){
    int index = 1 , tmpNum[MAXN*2];
    for(int i = 0 ; i < pos ; i++){
       tmpNum[index++] = num[i];
       if(num[i+1]-num[i] > 1)
          tmpNum[index++] = num[i]+1;
    }
    pos = index;
    memcpy(num , tmpNum , sizeof(num));
}

int search(int x){
    int left , right , mid;
    left = 1 , right = pos-1;
    while(left <= right){
       int mid = (left+right)>>1;
       if(num[mid] == x) 
           return mid;
       else if(num[mid] < x)
           left = mid+1;
       else
           right = mid-1;
    }
}

void buildTree(int left , int right , int pos){
    node[pos].left = left;
    node[pos].right = right;
    node[pos].mark = 0;
    if(left == right)
      return;
    int mid = (left+right)>>1;
    buildTree(left , mid , pos<<1);
    buildTree(mid+1 , right , (pos<<1)+1);
}

void push_down(int pos){
    if(node[pos].mark){
       node[pos<<1].mark = node[pos].mark;
       node[(pos<<1)+1].mark = node[pos].mark;
       node[pos].mark = 0;
    }
}

void update(int left , int right , int value , int pos){
    if(left <= node[pos].left && right >= node[pos].right){
       node[pos].mark = value;
       return;
    }
    push_down(pos);
    int mid = (node[pos].left + node[pos].right)>>1;
    if(right <= mid)
       update(left , right , value , pos<<1);
    else if(left > mid)
       update(left , right , value , (pos<<1)+1);
    else{
       update(left , mid , value , pos<<1);
       update(mid+1 , right , value , (pos<<1)+1);
    }
}

int query(int index , int pos){
    if(node[pos].left == node[pos].right)
      return node[pos].mark;
    push_down(pos);
    int mid = (node[pos].left + node[pos].right)>>1;
    if(index <= mid)
       return query(index , pos<<1);
    else
       return query(index , (pos<<1)+1);
}

int main(){
    int Case , cnt;
    int x , y;
    scanf("%d" , &Case);
    while(Case--){
       scanf("%d" , &n);
       pos = 0 , cnt = 0;
       for(int i = 0 ; i < n ; i++){
          scanf("%d%d" , &tmp[i].left , &tmp[i].right);
          num[pos++] = tmp[i].left , num[pos++] = tmp[i].right;
       }
       //离散化
       sort(num , num+pos);
       pos = unique(num , num+pos)-num;
       hash_map();   
       for(int i = 0 ; i < n ; i++){
          int index = search(tmp[i].left);
          tmp[i].left = index;
          index = search(tmp[i].right);
          tmp[i].right = index;
       }
       buildTree(1 , pos-1 , 1);
       for(int i = 0 ; i < n ; i++)
           update(tmp[i].left , tmp[i].right , ++cnt , 1);
       s.clear();
       for(int i = 1 ; i < pos ; i++)
           s.insert(query(i , 1));
       printf("%d\n" , s.size());
    }
    return 0;
}