HDU 4022 Bombing(11年上海 二分)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出一些点，给出两个操作，分别 是去掉横坐标为某个值的点，或者去掉纵坐标为某个值的点，问每次去掉点的个数
http://acm.hdu.edu.cn/showproblem.php?pid=4022
由于是分X,Y操作的，那么把X,Y分开，排序，然后针对操作，二分查找
全局变量记录某个点是否被去掉
排序+二分+暴力标记
哎，大清早的来一发水题，好忧桑
#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<algorithm>#include<set>#define inf 110000000#define M 10005#define N 100005#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))#define LL long long#define MOD 1000000007using namespace std;struct Node{ int val,id;}x[N],y[N];int n,q;int flag[N];bool cmp(Node n1,Node n2){ return n1.val<n2.val;}int BinSearch(Node *a,int n,int m){ int low=0,high=n-1,mid,pos=-1; while(low<=high){ mid=(low+high)/2; if(a[mid].val==m){pos=mid;break;} if(a[mid].val<m) low=mid+1; else high=mid-1; } if(pos==-1) return 0; int i=pos-1,ans=0; while(i>=0&&a[i].val==m){ if(flag[a[i].id]==0){flag[a[i].id]=1;ans++;} i--; } while(pos<n&&a[pos].val==m){ if(flag[a[pos].id]==0){flag[a[pos].id]=1;ans++;} pos++; } return ans;}int main(){ while(scanf("%d%d",&n,&q)!=EOF&&n+q){ for(int i=0;i<n;i++){ scanf("%d%d",&x[i].val,&y[i].val); x[i].id=y[i].id=i; } sort(x,x+n,cmp); sort(y,y+n,cmp); mem(flag,0); while(q--){ int k,p; scanf("%d%d",&k,&p); if(k==0) printf("%d\n",BinSearch(x,n,p)); else printf("%d\n",BinSearch(y,n,p)); } puts(""); } return 0;}