本题的数据范围有点大,所以得使用map去进行离散化。由于map的key不能重,而一行里面又有多个y坐标,所以要用map里面套set的方式去求解。
在消除某一行的时候自然需要把这一行里面列相关的给消除掉,毕竟题上说了死人不能再死一次。让我奇怪的是得要用multiset?难道有可能在一个坐标处建立两个基地吗?
#include <bits/stdc++.h>
using namespace std;
int N, M;
map<int, multiset<int> > mpx;
map<int, multiset<int> > mpy;
int main() {
int x, y, c, d;
cin>>N>>M;
for (int i=0;i<N;i++) {
cin>>x>>y;
mpx[x].insert(y);
mpy[y].insert(x);
}
while (M--) {
int cnt = 0;
cin>>c>>d;
if (c==0) {
set<int>::iterator st = mpx[d].begin();
for (;st!=mpx[d].end();st++) {
mpy[*st].erase(d);
}
cout<<mpx[d].size()<<endl;
mpx[d].clear();
} else {
set<int>::iterator st = mpy[d].begin();
for (;st!=mpy[d].end();st++) {
mpx[*st].erase(d);
}
cout<<mpy[d].size()<<endl;
mpy[d].clear();
}
}
return 0;
}

京公网安备 11010502036488号