问题翻译: 这是一场残酷的战争，杀死了数百万人，摧毁了一系列城市。为了阻止它，让我们轰炸对手的基地。在巷战的情况下， 这似乎不是一项艰苦的工作，但是，你会遇到一个更困难的例子：讲述军队的功绩。在轰炸行动中，指挥官将派出一群轰炸机，其武器具有巨大的破坏力，可以摧毁一排内的所有目标。由于我们间谍的出色工作，所有对手基地的位置都被检测到并在地图上标记，因此，轰炸计划将发送给您。 具体来说，地图表示为一个 2D 平面，上面标有敌方基地的一些位置。轰炸机有条不紊地出动，每架轰炸机都会轰炸地图上的一条垂直线或水平线。然后你的指挥部希望你报告每架轰炸机将摧毁多少个基地。请注意，在计算后来轰炸机的功绩时，不会考虑被毁坏的基地。

输入 多个测试用例，每个测试用例以两个非负整数 N （N<=100,000） 和 M （M<=100,000） 开头，分别表示目标基地的数量和预定的轰炸机数量。在接下来的 N 行中，有一对整数 x 和 y，由单个空格分隔，表示每个对手的底面的位置坐标。以下 M 行描述了轰炸机，每行包含两个整数 c 和 d，其中 c 是 0 或 1，d 是绝对值不超过 1e9 的整数，如果 c = 0，则该轰炸机将轰炸线 x = d，否则 y = d。当 N = M = 0 且测试用例数不超过 50 时，输入将结束。

输出 对于每个测试用例，输出 M 行，第 i 行包含一个整数，表示输入中被相应轰炸机摧毁的碱基数。在每个测试用例后输出一个空行。

// \n是换行

样本输入 3 2\n 1 2\n 1 3\n 2 3\n 0 1\n 1 3\n 0 0\n

示例输出 2 1 \n

前言:在这一道题,我们开始接触map和set数据结构

思路:为什么这道题要用map?因为行和列是1e9的数量级,显然不能顺序存储,所以考虑离散化存储,只存有敌人的行和列,实现离散化存储:用map

为什么要用multi set?因为set也是离散的,用multi是因为这一道题输入的点有重复的(虽然样例输入中没体现出来?)

为什么要将两者结合起来?因为炸掉某一行也会影响对应的列,我们用map表示某一行(列),multiset表示这一行中当前拥有敌人的列(行),实现了离散化的一对多,不用将每一行的每一列都存起来(存不下)

最终实现了行和列不重复计数 思路&AC代码:

#include<map>
#include<set>
#include<iostream>
using namespace std;
using line = map<int, multiset<int>>;//某一行(列),及其中有元素的列(行)
line mx;//行
line my;//列
long long bomb(line &a, line &b,int pos) {
    long long tmp=a[pos].size();//炸毁的这一行(列)有的元素
  
    for (auto it=a[pos].begin();it!=a[pos].end();++it) {
        b[*it].erase(pos);//在这一行(列)每个元素对应的列(行)中,清空这个行(列),保证了不重复计数
    }
    a[pos].clear();//炸毁这一行(列)
    return tmp;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,m,tx,ty,tc,td;
    while (true)
    {
        cin>>n>>m;
        if (n==0 && m==0) {break;}//按照题目输入要求
      	//每次输入不同样例前要清空
        mx.clear();
        my.clear();
        for (int i=1;i<=n;i++) {
            cin>>tx>>ty;
            mx[tx].insert(ty);//hang.insert(lie)
            my[ty].insert(tx);//lie.insert(hang),这样就实现了十字行列相互影响(炸毁绑定,不会重复炸毁)
        }
        long long res;
        for (int i=1;i<=m;i++) {
            cin>>tc>>td;
            if (tc==0) {res=bomb(mx,my,td);}
            else {res=bomb(my,mx,td);}//这样就不用写两个bomb了,炸毁某一行,处理对其他列的影响.等价于炸毁某一列对其他行的影响
            cout<<res<<'\n';//每一次炸毁都输出本次炸毁人数
        }
        cout<<'\n';//每个样例后回车
    }
    return 0;
}