今天真是各种sb,弱爆了。
果然以后做网预的时候就应该第一道水题用STL各种水。
闲话少说。
本题题意略,直接说做法。
首先,必需的是离散化。sort+MAP是我的离散化方法,个人觉得这样虽然慢,但是好写。
后面的就八仙过海各显神通了。什么用十字链表模拟啊,什么multiset啊,什么vector啊,什么数组直接标记啊,不一而足,水题就要用水题的方法做。
我是vector做的。
开了200000个vector分别用来存储离散化后的每行及每列中元素的个数。
每次查询的时候,将对应行/或者列的size输出,然后对其中每个元素在另外一边(行/列)用upper/lower_bound查存在性,存在的都删除erase,然后将本行/列清空clear。
一开始就是WA在此处了,因为有重复坐标的点,而set的一般写法无法处理这种情况,想了半天最后用了vector+二分。太蛋疼了。
还RE了一次,因为对于vector来说,erase作为动态删除会使其周围元素的指针改变,会发生内存泄漏、指针悬挂等现象,所以果断要用erase的范围删除操作[low,up)。
没啥说的,复杂度均摊下来很小,因为不会重复统计,所以顶多是NlogN的复杂度,再加上离散化的复杂度,整体NlogN。
老话,STL能做,为啥要手写?出题卡STL的就是sb,不解释;至于什么叫卡STL,各位大牛都懂得。
今天弱爆了,就这样吧。
附代码:
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 100005
struct point
{
int x,y;
point(){}
point(int a,int b):x(a),y(b){}
}p[maxn];
int x[maxn],y[maxn];
int n,m;
vector <int> X[maxn],Y[maxn];
map <int,int> MX,MY;
vector <int> ::iterator xlow,xup,ylow,yup,idx,idy;
int main()
{
while(scanf("%d %d",&n,&m) == 2 && (n || m))
{
MX.clear();
MY.clear();
for(int i = 1;i <= n;i++)
{
if(!X[i].empty())
X[i].clear();
if(!Y[i].empty())
Y[i].clear();
}
for(int i = 0;i < n;i++)
{
int a,b;
scanf("%d %d",&a,&b);
p[i] = point(a,b);
x[i] = a;
y[i] = b;
}
sort(x,x + n);
sort(y,y + n);
int cntx = 1,cnty = 1;
for(int i = 0;i < n;i++)
{
if(MX[x[i]] == 0)
MX[x[i]] = cntx++;
if(MY[y[i]] == 0)
MY[y[i]] = cnty++;
}
for(int i = 0;i < n;i++)
{
p[i].x = MX[p[i].x];
p[i].y = MY[p[i].y];
idx = lower_bound(X[p[i].x].begin(),X[p[i].x].end(),p[i].y);
X[p[i].x].insert(idx,p[i].y);
idy = lower_bound(Y[p[i].y].begin(),Y[p[i].y].end(),p[i].x);
Y[p[i].y].insert(idy,p[i].x);
}
for(int i = 0;i < m;i++)
{
int mod,d;
scanf("%d %d",&mod,&d);
if(mod == 0)
{
d = MX[d];
printf("%d\n",X[d].size());
if(X[d].empty())
continue;
for(idx = X[d].begin();idx != X[d].end();idx++)
{
int p = *idx;
ylow = lower_bound(Y[p].begin(),Y[p].end(),d);
yup = upper_bound(Y[p].begin(),Y[p].end(),d);
Y[p].erase(ylow,yup);
}
X[d].clear();
}
else
{
d = MY[d];
printf("%d\n",Y[d].size());
if(Y[d].empty())
continue;
for(idy = Y[d].begin();idy != Y[d].end();idy++)
{
int p = *idy;
xlow = lower_bound(X[p].begin(),X[p].end(),d);
xup = upper_bound(X[p].begin(),X[p].end(),d);
X[p].erase(xlow,xup);
}
Y[d].clear();
}
}
puts("");
}
}