[COCI Croatian Olympiad in Informatics 【hrastovi】]【二分】【各种排序】

【题目链接】http://www.hsin.hr/coci/
【题目大意】
给定N个点和Q个矩形。
对于每个矩形，求有多少个点落在其边界上。
【算法分析】
把一个矩形分成4条线段。然后分别处理。
可以先处理x=k的线段。
就是，把点按x为第一关键字，y为第二关键字排序。
然后对于每个x=k的线段，然后二分出对应范围，弄个Sum数组搞一下。就可以了。
对于y=k的线段，类似地处理。
就可以很快地搞定。
【其它】1Y。
【CODE】
#include #include #include struct Point{int x,y;}p[300005];
struct Ques{int x1,y1,x2,y2;}Q[100005];
struct Line{int key,l,r,pos;}L[200005];
int n,Qt,Lt;
int Sum[300005],ans[100005];

void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
scanf("%d",&Qt);
for (int i=1;i<=Qt;i++)
scanf("%d%d%d%d",&Q[i].x1,&Q[i].y1,&Q[i].x2,&Q[i].y2);
}

int cmpx_p(const void *A,const void *B){
if ( ((Point*)A)->x != ((Point*)B)->x ) return ((Point*)A)->x-((Point*)B)->x;
return ((Point*)A)->y-((Point*)B)->y;
}

int cmp_L(const void *A,const void *B){
return ((Line*)A)->key-((Line*)B)->key;
}

int Findx_l(int st,int ed,int y){
int l=st,r=ed,mid;
while (l mid=(l+r)/2;
if (y<=p[mid].y) r=mid;
else l=mid+1;
}
if (y<=p[l].y) return l;
return 0x7FFFFFFF;
}

int Findx_r(int st,int ed,int y){
int l=st,r=ed,mid;
while (l mid=(l+r+1)/2;
if (p[mid].y<=y) l=mid;
else r=mid-1;
}
if (p[l].y<=y) return l;
return -0x7FFFFFFF;
}

void solvex(){
int i,j,stp,edp,stL,edL,l,r;
Lt=0;
for (i=1;i<=Qt;i++){
L[++Lt].l=Q[i].y1; L[Lt].r=Q[i].y2; L[Lt].pos=i; L[Lt].key=Q[i].x1;
L[++Lt].l=Q[i].y1; L[Lt].r=Q[i].y2; L[Lt].pos=i; L[Lt].key=Q[i].x2;
}
qsort(p+1,n,sizeof(Point),cmpx_p);
qsort(L+1,Lt,sizeof(Line),cmp_L);
edL=1;
for (i=1;i<=n;i=edp+1){
stp=i;
for (edp=i;edp for (stL=edL;stL<=Lt && L[stL].key for (edL=stL;edL if (stL>Lt || L[stL].key!=p[i].x) continue;
for (j=stp;j<=edp;j++) Sum[j]=j-stp+1;
for (j=stL;j<=edL;j++){
l=Findx_l(stp,edp,L[j].l);
r=Findx_r(stp,edp,L[j].r);
if (l>r) continue;
ans[L[j].pos]+=Sum[r]-Sum[l]+1;
}
}
}

int cmpy_p(const void *A,const void *B){
if ( ((Point*)A)->y != ((Point*)B)->y ) return ((Point*)A)->y-((Point*)B)->y;
return ((Point*)A)->x-((Point*)B)->x;
}

int Findy_l(int st,int ed,int x){
int l=st,r=ed,mid;
while (l mid=(l+r)/2;
if (x<=p[mid].x) r=mid;
else l=mid+1;
}
if (x<=p[l].x) return l;
return 0x7FFFFFFF;
}

int Findy_r(int st,int ed,int x){
int l=st,r=ed,mid;
while (l mid=(l+r+1)/2;
if (p[mid].x<=x) l=mid;
else r=mid-1;
}
if (p[l].x<=x) return l;
return -0x7FFFFFFF;
}

void solvey(){
int i,j,stp,edp,stL,edL,l,r;
Lt=0;
for (i=1;i<=Qt;i++){
L[++Lt].l=Q[i].x1+1; L[Lt].r=Q[i].x2-1; L[Lt].pos=i; L[Lt].key=Q[i].y1;
if (L[Lt].l>L[Lt].r) Lt–;
L[++Lt].l=Q[i].x1+1; L[Lt].r=Q[i].x2-1; L[Lt].pos=i; L[Lt].key=Q[i].y2;
if (L[Lt].l>L[Lt].r) Lt–;
}
qsort(p+1,n,sizeof(Point),cmpy_p);
qsort(L+1,Lt,sizeof(Line),cmp_L);
edL=1;
for (i=1;i<=n;i=edp+1){
stp=i;
for (edp=i;edp for (stL=edL;stL<=Lt && L[stL].key for (edL=stL;edL if (stL>Lt || L[stL].key!=p[i].y) continue;
for (j=stp;j<=edp;j++) Sum[j]=j-stp+1;
for (j=stL;j<=edL;j++){
l=Findy_l(stp,edp,L[j].l);
r=Findy_r(stp,edp,L[j].r);
if (l>r) continue;
ans[L[j].pos]+=Sum[r]-Sum[l]+1;
}
}
}

int main(){
// freopen("HRASTOVI.in","r",stdin);
// freopen("HRASTOVI.out","w",stdout);
init();
solvex();
solvey();
for (int i=1;i<=Qt;i++) printf("%dn",ans[i]);
return 0;
}