11年上海赛区赛真题 Bombing

#include<cstdio>#include<iostream>#include<algorithm>using namespace std;struct node{ int x; int y; int f;}arrx[100002],arry[100002]; //每个点的信息，坐标及其序号（输入时的序号）bool flag[100002]; //记录相关序号的点是否被访问过，访问过标为“true”，否则标为“false”int n,m;bool cmpx(node a,node b) //按x从小到大排序{ return a.x<b.x;}bool cmpy(node a,node b) //按y从小到大排序{ return a.y<b.y;}int findx(int x) //二分法查找第一个x与给定x相等的坐标的结构体数组下标{ int l=0,r=n-1,mi; while(l<r) { mi=(l+r)/2; if(arrx[mi].x>=x)r=mi; else l=mi+1; } return l;}int findy(int y) //二分法查找第一个y与给定y相等的坐标的结构体数组下标{ int l=0,r=n,mi; while(l<r) { mi=(l+r)/2; if(arry[mi].y>=y)r=mi; else l=mi+1; } return l;}int main(){ int x,y; int i,j; while(scanf("%d%d",&n,&m)&&n+m) { for(i=0;i<n;i++) { scanf("%d%d",&x,&y); arrx[i].x=x,arrx[i].y=y,arrx[i].f=i; //初始化x值查询数组的信息 arry[i].x=x,arry[i].y=y,arry[i].f=i; //初始化y值查询数组的信息 flag[i]=false; //初始化访问标记变量（都未访问） } sort(arrx,arrx+n,cmpx); //x值查询数组以x为标准排序，利于二分查找 sort(arry,arry+n,cmpy); while(m--) //m组询问 { int sum=0; scanf("%d%d",&x,&y); if(!x) //查询以x为基准 { i=findx(y); //在x值查询数组中，下标为i的坐标是第一个x=y的点 for(;i<n;i++) { if(arrx[i].x!=y)break; //直到坐标的x值不等于y或访问到数组末尾，结束循环 else if(!flag[arrx[i].f]) //该点未访问 flag[arrx[i].f]=true,sum++; //标记为访问并且改变计数变量 } } else //同上 { i=findy(y); for(;i<n;i++) { if(arry[i].y!=y) break; else if(!flag[arry[i].f]) flag[arry[i].f]=true,sum++; } } printf("%d\n",sum); } printf("\n"); } return 0;}