poj2528离散化+线段树

题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报

这题如果不离散化，最大值10000000，数组会超内存，所以应该把每一张海报的左右边进行存储更新，然后排序，把这些边离散化到1~m的线段树中，就不会超内存，因为输入数据的个数的最大值为10000。

这题就做法就是先离散化，然后用二分查找找到每次输入的左边界和右边界在数组中的位置，然后利用线段树更新，最后利用线段树查询一下即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int Max=11110;
bool hash[Max];
int li[Max],ri[Max];
int x[Max<<2],col[Max<<4];
int cnt;
void update(int l,int r,int rt,int c,int L,int R){
if(L<=l&&r<=R){
col[rt]=c;
return;
}
if(col[rt]!=-1){
col[rt<<1]=col[rt<<1|1]=col[rt];
col[rt]=-1;
}
int m=(l+r)>>1;
if(L<=m)update(l,m,rt<<1,c,L,R);
if(m<R)update(m+1,r,rt<<1|1,c,L,R);
}
void query(int l,int r,int rt){
if(col[rt]!=-1){
if(!hash[col[rt]])
cnt++;
hash[col[rt]]=true;
return;
}
if(l==r)
return ;
int m=(l+r)>>1;
query(l,m,rt<<1);
query(m+1,r,rt<<1|1);
}
int bin(int a,int n){
int l=0,r=n-1;
while(l<=r){
int m=(l+r)>>1;
if(x[m]==a)
return m;
if(x[m]<a){
l=m+1;
}
else
r=m-1;
}
return -1;
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(hash,0,sizeof(hash));
memset(col,-1,sizeof(col));
int t=0;
cnt=0;
for(int i=0;i<n;i++){
scanf("%d%d",&li[i],&ri[i]);
x[t++]=li[i];
x[t++]=ri[i];
}
sort(x,x+t);
int m=1;
for(int i=1;i<t;i++){
if(x[i]!=x[i-1]){
x[m++]=x[i];
}
}
for(int i=0;i<n;i++){
int l=bin(li[i],m);
int r=bin(ri[i],m);
update(0,m,1,i,l,r);
}
query(0,m,1);
printf("%dn",cnt);
}
return 0;
}

最后

以上就是小巧老师为你收集整理的poj2528离散化+线段树的全部内容，希望文章能够帮你解决poj2528离散化+线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。