# poj 2528 Mayor's posters

+关注继续查看

1 首先这一题的数据是错误的，这题的区间的最大值为10000000，如果我们按照正常的线段树的思路去做的话肯定是会超内存和超时的。
2 所以我们应该考虑离散化，我们把区间离散成集中的区间。但是这个地方会有个问题

#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;
}


|
10月前
|

POJ 2431-Expedition

50 0
POJ 2027 No Brainer
POJ 2027 No Brainer
66 0
|

|
Windows
POJ 1067 取石子游戏

1053 0
|

poj-1005-l tanink i need a houseboat
Description Fred Mapper is considering purchasing some land in Louisiana to build his house on. In the process of investigating the land, he learned ...
907 0
|

poj题目分类
http://www.cnblogs.com/kuangbin/archive/2011/07/29/2120667.html
751 0
|

poj1273Drainage Ditches
1 #include 2 /* 3 题意：就是寻找从源点到汇点的最大流！ 4 要注意的是每两个点的流量可能有多个，也就是说有重边，所以要把两个点的所有的流量都加起来 5 就是这两个点之间的流量了！ 6 ...
800 0