题意：有一面墙，被等分为1QW份，一份的宽度为一个单位宽度。现在往墙上贴N张海报，每张海报的宽度是任意的，但是必定是单位宽度的整数倍，且<=1QW。后贴的海报若与先贴的海报有交集，，后贴的海报必定会全部或局部覆盖先贴的海报。现在给出每张海报所贴的位置（左端位置和右端位置），问张贴完N张海报后，还能看见多少张海报？（PS：看见一部分也算看到。）
思路：简单的成段更新，但是数据量是1千万，会MT，所以要区间压缩（离散化），保证覆盖的关系不变，离散化的时候有个易错的细节，poj数据水了，这个易错点引用hh牛的话：
而这题的难点在于每个数字其实表示的是一个单位长度(并非一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)给出下面两个简单的例子应该能体现普通离散化的缺陷:例子一: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是否被完全覆盖掉了呢?例子一是完全被覆盖掉了,而例子二没有被覆盖
//1412 KB 79 ms#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define M 10005#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int col[M*16];int poi[M*4]; //因为经过了特殊化处理，所以在2*M的基础上又放大了一倍int li[M],ri[M];bool book[M];void build(int l,int r,int rt){col[rt]=-1;if(l==r) return;int m=(l+r)>>1;build(lson);build(rson);}int Bin(int g,int m) //二分出离散后的序号{int l=0,r=m-1;while(r>=l){int mid=(l+r)>>1;if(poi[mid]==g) return mid;else if(poi[mid]>g) r=mid-1;else l=mid+1;}}void pushdown(int rt){if(col[rt]==-1) return ;col[rt<<1]=col[rt<<1|1]=col[rt];col[rt]=-1;}void update(int L,int R,int c,int l,int r,int rt){if(L<=l&&r<=R){col[rt]=c;return;}pushdown(rt);int m=(l+r)>>1;if(L<=m) update(L,R,c,lson);if(R>m) update(L,R,c,rson);}int query(int l,int r,int rt){int ans=0;if(col[rt]!=-1){if(!book[col[rt]]){book[col[rt] ]=true;ans++;}return ans;}if (l == r) return 0;int m=(l+r)>>1;ans+=query(lson);ans+=query(rson);return ans;}int main(){int cas,n;scanf("%d",&cas);while(cas–){scanf("%d",&n);int cnt=0;for(int i=1;i<=n;i++){scanf("%d%d",&li[i],&ri[i]);poi[cnt++]=li[i];poi[cnt++]=ri[i];}sort(poi,poi+cnt);int top=1;for(int i=1;i<cnt;i++){if(poi[i]!=poi[i-1]){ //去重poi[top++]=poi[i];}}int tmp=top;for(int i=1;i<tmp;i++){ //特殊化处理if(poi[i]-poi[i-1]>1){poi[top++]=poi[i-1]+1;}}sort(poi,poi+top);build(0,top-1,1);int c=0; //待标记的颜色for(int i=1;i<=n;i++){int l=Bin(li[i],top);int r=Bin(ri[i],top);update(l,r,++c,0,top-1,1);}memset(book,0,sizeof(book));printf("%d\n",query(0,top-1,1));}return 0;}
人爱美，不仅需要服饰居室之美，还需要心灵品德之美。
