poj 2528Mayor's posters
http://acm.pku.edu.cn/JudgeOnline/problem?id=2528
離散化+線段樹
Source Code
| Problem: 2528 |
|
User: lovecanon |
| Memory: 760K |
|
Time: 79MS |
| Language: C++ |
|
Result: Accepted |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int tree[20002*3+1],seg[20002][2],a[20002],point[20002],vis[20002],tot,sum_of_point,size;
int min(int a,int b){if(a<=b) return a;else return b;}
int max(int a,int b){if(a>=b) return a;else return b;}
int cmp(const void *a,const void *b){
return *(int *)a-*(int *)b;
}
int binary_search(int t){
int l=1,r=sum_of_point;
while(l<=r){
int m=(l+r)/2;
if(point[m]==t) return m;
else if(point[m]>t) r=m-1;
else l=m+1;
}
return l;
}
void modify(int l,int r,int c,int L,int R,int t){
if(l==L&&r==R||tree[t]==c) {tree[t]=c;return ;}
if(tree[t]!=-1) tree[t*2]=tree[t*2+1]=tree[t];
tree[t]=-1;
int m=(L+R)/2;
if(l<m) modify(l,min(m,r),c,L,m,t*2);
if(r>m) modify(max(l,m),r,c,m,R,t*2+1);
}
void query(int t,int L,int R){
if(tree[t]!=-1&&tree[t]!=0){
int i;
for(i=L;i<R;i++) a[i]=tree[t];
}
else if(tree[t]!=0){
query(t*2,L,(L+R)/2);
query(t*2+1,(L+R)/2,R);
}
}
int main(){
int i,T,N,x,y;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
tot=0;
for(i=1;i<=N;i++){
scanf("%d%d",&x,&y);
seg[i][0]=x;seg[i][1]=y+1;
a[++tot]=x;a[++tot]=y+1;
}
qsort(a+1,tot,sizeof(a[0]),cmp);
sum_of_point=0;point[++sum_of_point]=a[1];
for(i=2;i<=tot;i++)
if(a[i]!=a[i-1]) point[++sum_of_point]=a[i];
size=sum_of_point;
tree[1]=0;
for(i=1;i<=N;i++){
x=binary_search(seg[i][0]);
y=binary_search(seg[i][1]);
modify(x,y,i,1,size,1);
}
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
query(1,1,size);
int tmp=-2,ret=0;
for(i=1;i<size;i++){
if(a[i]==tmp) continue;
else{
tmp=a[i];
if(tmp!=0&&!vis[tmp]) {vis[tmp]=1;ret++;}
}
}
printf("%d\n",ret);
}
return 0;
}