Problem: 2528 | User: qq1203456195 | |
Memory: 1120K | Time: 94MS | |
Language:C++ | Result: Accepted |
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 11111 int hash[maxn]; int li[maxn],ri[maxn]; int X[maxn<<4]; int col[maxn<<4];//maxn张海报对应maxn<<1个边界,最多需要添加maxn<<1个辅助点,即的线段树要((maxn<<1)<<1)<<2个结点。 int cnt; void PushDown(int rt)//lazy标志位下传 { if(col[rt]!=-1) { 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) { int m=(l+r)>>1; if(L<=l&&r<=R) { col[rt]=C; return; } PushDown(rt); if (L<=m) update(L,R,C,lson); if (m< R) update(L,R,C,rson); } void query(int l,int r,int rt) { int m=(l+r)>>1; if(col[rt]!=-1) { if(!hash[col[rt]]) cnt++; hash[col[rt]]=1; return; } if(l==r) return; query(lson); query(rson); } int Bin(int key,int len,int *x)//在长度为len的数组中二分查找key的位置 { int l=0,r=len; int m; while(l<=r) { m=(l+r)>>1; if(x[m]==key) return m; if(x[m]<key) l=m+1; else r=m-1; } return -1; } int main() { int i,m,n,p,cas,L,R,C; scanf("%d",&cas); while (cas--) { scanf("%d",&n); //读取数据,并构造待离散化数组X,离散化第一步 p=0; for (i=0;i<n;i++) { scanf("%d%d",&li[i],&ri[i]); X[p++]=li[i]; X[p++]=ri[i]; } //将X内数据排序,离散化第二步(注意数据范围:x[0]...x[p-1]) sort(X,X+p); //去掉X内重复值,离散化第三步 /*从1开始,到p-1为止*/ m=1; for (i=1;i<p;i++) { if(X[i]!=X[i-1])//如果不等,说明没有出现过,就保留;否则就丢弃。 X[m++]=X[i]; } /*难点!如果出现1,2,5,9这种数据,就改成1,2,5,6,9 也就是说如果相邻数字间距大于1的话,在其中加上任意一个和相邻数字中的某个数字 差值为1的数字 */ for (i=m-1;i>0;i--) { if(X[i]!=X[i-1]+1) X[m++]=X[i-1]+1; } sort(X,X+m);//(注意数据范围:x[0]...x[m-1]) //离散化结束,只需建立叶子节点为m的线段树即可,X[m]的值就是输入的数据中的一个。 //为了统计海报的个数,就需要海报的标记,而li,ri的下标就可以做海报的标记 //创建线段树 memset(col,-1,sizeof(col)); for (i=0;i<n;i++) { L=Bin(li[i],m-1,X); R=Bin(ri[i],m-1,X); C=i; update(L,R,C,0,m,1); } //统计海报个数 cnt=0; memset(hash,0,sizeof(hash)); query(0,m,1); printf("%d\n",cnt); } return 0; }
本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/05/11/2496536.html,如需转载请自行联系原作者