poj2528Mayor's posters

posters"/>

poj2528Mayor's posters

题目分析

大水题
既然这么水我就不写分析了。
好吧还是写，就是离散化，为了方便，我用了map,事实上也并没有卡不过时限，不过慢一些了是真的。
拿样例来说吧。
1 4
2 6
8 10
3 4
7 10
我们排序得到（其实不排序也行，map的遍历是按照顺序遍历的）：
1 2 3 4 6 7 8 10
然后我们就这样离散：
1->1
2->2
3->3
4->4
6->5
7->6
8->7
10->8
然后我们的墙就一点也没有浪费，这以过程可以用map实现（因为map是真爱啊～stl大法好，弃c转c++保平安）
染色的时候用-1表示不是整块色块。
找答案时也用map表示出现的色块，发现整块色块直接返回。
就是这样，喵～

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<map>
using namespace std;
int read(){int q=0;char ch=' ';while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();return q;
}
int T,n;
map<int,int>fi,shu;
int col[80005];//-1表示不只一种颜色,0表示没有海报
int ll[10005],rr[10005],hi[20005];
void pd(int s,int t,int i){int mid=(s+t)>>1;col[(i<<1)]=col[i];col[(i<<1)|1]=col[i];
}
void pat(int l,int r,int s,int t,int i,int num){if(l<=s&&t<=r){col[i]=num;return;}if(col[i]>=0)pd(s,t,i);int mid=(s+t)>>1;if(l<=mid)pat(l,r,s,mid,(i<<1),num);if(mid+1<=r)pat(l,r,mid+1,t,(i<<1)|1,num);col[i]=-1;
}
void getans(int s,int t,int i){if(col[i]>=0){shu[col[i]]=1;return;}int mid=(s+t)>>1;getans(s,mid,(i<<1));getans(mid+1,t,(i<<1)|1);
}
int main()
{int i,j,x,y,m,cnt;T=read();while(T--){n=read();cnt=0;fi.clear();shu.clear();m=0;for(i=1;i<=n;i++){ll[i]=read();rr[i]=read();hi[++m]=ll[i];hi[++m]=rr[i];}sort(hi+1,hi+m+1);for(i=1;i<=m;i++)if(!fi.count(hi[i]))fi[hi[i]]=++cnt;col[1]=0;for(i=1;i<=n;i++)   pat(fi[ll[i]],fi[rr[i]],1,cnt,1,i);getans(1,cnt,1);m=shu.size();printf("%d\n",m);}return 0;
}