SP9512 题解

前言

RMJ 炸了，建议在 vjudge 上提交。

SP9512

vjudge

题目大意

给定坐标系上的一些点（可能有重复），每次操作移除一列或一行的所有点，问你每次操作能移除多少点（已经移除的点不再统计）。

思路

首先来看最基础的想法。
将坐标系记录，每次删除就一个一个“抹零”。

但这样的话坐标系的空间复杂度就会达到 $O(10^{18})$。数组肯定存不下。

$d$ 很大，看来是没办法往这边想了。

注意到 $N$ 相较于 $d$ 要小很多，所以能不能优化一下呢？

由于每次操作都是抹除一列或一行，所以我们可以这样记录：

• xfindy[i][j] 表示 x 坐标为 $i$ 时第 $j$ 个点的 y 坐标。

• yfindx[i][j] 表示 y 坐标为 $i$ 时第 $j$ 个点的 x 坐标。

于是就有了第二种想法：记录每一列/行有的点，统一删除。
空间复杂度为 $O(dN)$，好了一点。

这样算是解决了一半，因为如果统一删去一列/行，另一个数组还是要逐个删。

来个图理解一下：

如果我要删去第 $1$ 列，xfindy[1] 是可以直接清空，可是 yfindx[i]
，$i \in [0,3]$ 里面还要逐一寻找啊。

这时间复杂度有多 $O(N)$ 啊。

于是第三种做法：map+set。

将原先的 xfindy 改成 map<int,set<int> > xfindy，
yfindx 同理。

那就好办了，set 每次操作的复杂度都是 $\log$ 的，省下了例子中在 yfindx[i]，$i \in [0,3]$ 里寻找。如果不是例子也可以这样优化。

只要 SPOJ 不出毒瘤数据，就能过了。

诶 set 不能重复计算啊，怎么办？
multiset！

看看代码吧。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,multiset<int> > xfindy;
map<int,multiset<int> > yfindx;
void each(){
	xfindy.clear();
	yfindx.clear();
	for(int i=1;i<=n;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		if(xfindy.count(x)==0){//如果这一行没有，特判加入
			multiset<int> tmp={y};
			xfindy.insert({x,tmp});
		}
		else{
			(*xfindy.find(x)).second.insert(y);//有的话直接加就好
		}
		if(yfindx.count(y)==0){
			multiset<int> tmp={x};
			yfindx.insert({y,tmp});
		}
		else{
			(*yfindx.find(y)).second.insert(x);
		}
	}
	for(int i=1;i<=m;++i){
		int sw,d;
		scanf("%d%d",&sw,&d);
		if(sw==0){//删除列
			if(!xfindy.count(d)) printf("0\n");
			else {
				printf("%d\n",(*xfindy.find(d)).second.size());//输出大小
				multiset<int> del=xfindy.find(d)->second;
				xfindy.erase(xfindy.find(d));//直接清空
				for(multiset<int>::iterator j=del.begin();j!=del.end();++j){
				//迭代器，迭代需要删除点的y坐标
					yfindx[*j].erase(d);//使用erase优化复杂度。
				}
			}
		}
		else{//删除行
			if(!yfindx.count(d)) printf("0\n");
			else {
				printf("%d\n",(*yfindx.find(d)).second.size());
				multiset<int> del=yfindx.find(d)->second;
				yfindx.erase(yfindx.find(d));
				for(multiset<int>::iterator j=del.begin();j!=del.end();++j){
					xfindy[*j].erase(d);
				}	
			}
		}
	}
}
int main(){
	while(1){//多测
		scanf("%d%d",&n,&m);
		if(n==0&&m==0) return 0;
		each();
	}
	
	return 0;
}