poj 2528 Mayor's posters線分樹+離散話!!!
2544 ワード
re , , !!!
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
int l;
int r;
int s;
}a[400000];
int b[100005],c[100005],d[100005],e[100005],ans,n;
void buildtree(int i,int left,int right){///
a[i].l=left;
a[i].r=right;
a[i].s=-1;
if(a[i].l==a[i].r)
return ;
int mid=(left+right)/2;
buildtree(i*2,left,mid);
buildtree(i*2+1,mid+1,right);
}
void insert(int i,int left,int right,int sum){/// !!
if((a[i].l!=a[i].r) &&(a[i].s!=-1)){///
a[i*2].s=a[i].s;
a[i*2+1].s=a[i].s;
a[i].s=-1;
}
if(left==a[i].l&&right==a[i].r){///
a[i].s=sum;
return ;
}
int mid=(a[i].l+a[i].r)>>1;
if(mid>=right)
insert(i*2,left,right,sum);
else
if(mid<left)
insert(i*2+1,left,right,sum);
else{
insert(i*2,left,mid,sum);
insert(i*2+1,mid+1,right,sum);
}
return ;
}
int find(int x,int cou){///
int l=1;int r=cou-1;
while(r>=l){
int mid=(l+r)>>1;
if(x>c[mid])
l=mid+1;
if(x<c[mid])
r=mid-1;
if(x==c[mid])
return mid;
}
return r;
}
void querry(int i){///
if(a[i].s!=-1){
if(d[a[i].s]==0){
ans++;d[a[i].s]=1;
}
return ;
}
if(a[i].l==a[i].r)
return ;
querry(i*2);
querry(i*2+1);
}
int main()
{
int ca,x,y;
scanf("%d",&ca);
while(ca--){
scanf("%d",&n);
for(int i=0;i<=n;i++)
d[i]=0;
int cou=0;
for(int i=0;i<n;i++){
scanf("%d",&b[cou++]);
scanf("%d",&b[cou++]);
}
for(int i=0;i<cou;i++)
e[i]=b[i];
sort(b,b+cou);
int couc=cou;
b[cou]=-1;
cou=1;
for(int i=0;i<couc;i++){/// , , ,
if(b[i]==b[i+1])
continue;
c[cou++]=b[i];
}
buildtree(1,1,cou-1);
int tx,ty;
int temp=1;
int te=0;
for(int i=0;i<n;i++){
int xx=find(e[te++],cou);
int yy=find(e[te++],cou);
insert(1,xx,yy,temp++);
}
ans=0;
querry(1);
printf("%d
",ans);
}
return 0;
}