题目大意：在二维平面上，给一些点。有两个操作：给一个d，把所有x为d的点去掉，或把所有y为d的点去掉，问每次去掉的点。
我的思路：
先将横纵坐标都离散化（大部分时间都花在这个上面吧），然后直接把出现过的点（离散过的点）累计，每次询问之后就可以直接输出了，之后再维护一下，把对应的x或y的累计值 减1
==! 很浅显的思路
我的代码：600+ms
View Code
#include<iostream>
#include<map>
using namespace std;
map<int,int> mapx;
map<int,int> mapy;
map<int,int>::iterator it1,it2;
int ex[200001];
struct ni
{
int v;
ni *next;
};
struct node
{
int v;
ni *next;//用链表保存对应的x值或y值
}p[200001];//直接对x和y离散化，所以总数有200000个
int main()
{
int n,m,k,a,b,x,y;
while(scanf("%d %d",&n,&m)==2&&(m||n))
{
mapx.clear();
mapy.clear();
int num=0;
it1=mapx.end();
it2=mapy.end();
memset(ex,0,sizeof(ex));
for(int i=0;i<n;i++)
{
scanf("%d %d",&x,&y);
if(it1==mapx.find(x))
{
a=num++;
mapx[x]=a;
p[a].next=NULL;
}
else a=mapx[x];
if(it2==mapy.find(y))
{
b=num++;
mapy[y]=b;
p[b].next=NULL;
}
else b=mapy[y];
ni *q=p[a].next,*temp=p[a].next;
while(q!=NULL)
{
temp=q;
q=q->next;
}
ni *newn=(ni *)malloc(sizeof(ni));
newn->v=b;//将x对应的y值插入对应的链表中
newn->next=NULL;
if(p[a].next==NULL)p[a].next=newn;
else temp->next=newn;
temp=q=p[b].next;
while(q!=NULL)
{
temp=q;
q=q->next;
}
newn=(ni*)malloc(sizeof(ni));
newn->v=a;//将y对应的x值插入对应的链表中
newn->next=NULL;
if(p[b].next==NULL) p[b].next=newn;
else
temp->next=newn;
ex[a]++;
ex[b]++;
}
while(m--)
{
scanf("%d %d",&k,&a);
if(k==0)
{
if(it1==mapx.find(a))
{
printf("0\n");continue;
}
x=mapx[a];
if(ex[x]>0)
printf("%d\n",ex[x]);
else printf("0\n");
mapx.erase(a);
ex[x]=0;
ni *q=p[x].next;
while(q!=NULL)
{
ex[q->v]--;
q=q->next;
}
}
else if(k)
{
if(it2==mapy.find(a))
{
printf("0\n");continue;
}
y=mapy[a];
if(ex[y]>0)
printf("%d\n",ex[y]);
else printf("0\n");
mapy.erase(a);
ex[y]=0;
ni *q=p[y].next;
while(q!=NULL)//维护操作
{
ex[q->v]--;
q=q->next;
}
}
}
printf("\n");
}
return 0;
}
其他的思路：快排+二分查找。300+ms
首先，每一个点都给一个唯一的编号，分两部分排序，对x和对y。然后暴力去点。
其实，这个我也想过，可是当时很执着的以为，每次询问都要排序，我的天呐，当时短路了
View Code
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct nd{
int x,y,s;
}ax[100005],ay[100005];
int vis[100005];
int cmpx(const void *a,const void *b){
struct nd *aa=(struct nd*)a;
struct nd *bb=(struct nd*)b;
return aa->x-bb->x;
}
int cmpy(const void *a,const void *b){
struct nd *aa=(struct nd*)a;
struct nd *bb=(struct nd*)b;
return aa->y-bb->y;
}
int bsx(int n,int val){
int l=1,h=n,m;
while( l<h ){
m=(l+h)/2;
if( ax[m].x>=val ) h=m;
else l=m+1;
}return l;
}
int bsy(int n,int val){
int l=1,h=n,m;
while( l<h ){
m=(l+h)/2;
if( ay[m].y>=val ) h=m;
else l=m+1;
}return l;
}
int main()
{
int i,j,t,k,x,y,n,m;
while( scanf("%d %d",&n,&m)==2 ){
if( m+n==0 ) break;
for( i=1; i<=n; i++ ){
scanf("%d%d",&x,&y);
ax[i].x=x; ax[i].y=y; ax[i].s=i;
ay[i].x=x; ay[i].y=y; ay[i].s=i;
vis[i]=0;
}
qsort(ax+1,n,sizeof(ax[0]),cmpx);
qsort(ay+1,n,sizeof(ay[0]),cmpy);
while( m-- ){
int ans=0;
scanf("%d%d",&t,&k);
if( t==0 ){
j=bsx(n,k);
for( i=j; i<=n; i++ ){
if( (ax[i].x==k) && !vis[ax[i].s] ) ans++;
else if( ax[i].x!=k ) break; //这里是重点，原来写的是ax[i].x!=ax[j].x
vis[ax[i].s]=1;
}
}
else{
j=bsy(n,k);
for( i=j; i<=n; i++ ){
if( (ay[i].y==k) && !vis[ay[i].s] ) ans++;
else if( ay[i].y!=k ) break;
vis[ay[i].s]=1;
}
}
printf("%d\n",ans);
}
puts("");
}return 0;
}