poj 2528 Mayor's posters（线段树+离散化）-白红宇

poj 2528 Mayor's posters

线段树 + 离散化

离散化的理解：

给你一系列的正整数，例如 1， 4 ， 100， 1000000000，如果利用线段树求解的话，很明显

会导致内存的耗尽。所以我们做一个映射关系，将范围很大的数据映射到范围很小的数据上

1---->1 4----->2 100----->3 1000000000----->4

这样就会减少内存一些不必要的消耗

建立好映射关系了，接着就是利用线段树求解

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#define N 10000010

#define M 10005

using namespace std;

class EDGE{

public:

int ld, rd;

};

int tree[M*16];//一共有M*2个端点,一个线段映射到四个点，左右端点，左端点-1，右端点+1，数组的大小是线段树最底层数据个数的4倍

EDGE edge[M];

int p[M*4];

int hash[N];

int n;

int insert(int p, int lr, int rr, int ld, int rd){

if(tree[p] && lr<=ld && rd<=rr)//如果当前的区间[ld, rd]被包含在[lr, rr]中，而且[lr, rr]的区间已经被覆盖

return 1;

else if(lr==ld && rr==rd){

tree[p]=1;

return 0;

}

else{

int mid=(lr+rr)>>1;

int f1, f2, f3, f4;

if(mid>=rd)

f1=insert(p<<1, lr, mid, ld, rd);

else if(mid<ld)

f2=insert(p<<1|1, mid+1, rr, ld, rd);

else{

f3=insert(p<<1, lr, mid, ld, mid);

f4=insert(p<<1|1, mid+1, rr, mid+1, rd);

}

tree[p]=tree[p<<1] && tree[p<<1|1];//两个子树都被覆盖的时候父类才会被覆盖

if(mid>=rd)

return f1;

else if(mid<ld)

return f2;

else return f3 && f4;

}

1 10

1 3

6 10

如果将一个线段离散化成两个点，输出地结果是2

如果是四个节点，输出的结果就是3

而正确的结果就是3

int main(){

int t, i, nm;

scanf("%d", &t);

while(t--){

int maxR=0;

scanf("%d", &n);

for(i=0; i<n; ++i){

scanf("%d%d", &edge[i].ld, &edge[i].rd);

p[maxR++]=edge[i].ld-1;

p[maxR++]=edge[i].ld;

p[maxR++]=edge[i].rd;

p[maxR++]=edge[i].rd+1;

}

sort(p, p+maxR);

maxR=unique(p, p+maxR)-p;//元素去重

for(i=0, nm=0; i<maxR; ++i){

hash[p[i]]=++nm;

}

memset(tree, 0, sizeof(tree));//初始值是所有的点都没有被覆盖

int ans=0;

for(i=n-1; i>=0; --i){//由外向里看真是个不错的主意

if(!insert(1, 1, nm, hash[edge[i].ld], hash[edge[i].rd]))

++ans;

}

printf("%d\n", ans);

}

return 0;

}

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3819362.html，如需转载请自行联系原作者