题解 T93270 【轰炸城市】

传送门

30%的题解：

• 直接每次询问枚举所有点。

60%的题解：

• 坐标值很小，可以尝试用链表，可以做到$O(n)$的时间复杂度

100%的题解：

• $map$套$multiset$

• $X$坐标开个$mapx$，里面存的是每个$X$坐标的不同$Y$坐标，这些$Y$坐标用$multiset$保存。

• $Y$坐标也同理开一个$mapy$。

• 统计点的时候，以平行于$y$轴的轰炸带为例，在$X$坐标的$mapx$中，枚举所有在$n1-n2$范围内的$x$，然后统计每个x里面所有的$y$，同时删去在$mapy$中对应的点，最后把$mapx$中$n1-n2$范围的所有元素都删掉。

• 时间复杂度$O(n \log n)$

• 也可以使用珂朵莉树。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#define MAXN 100010
using namespace std;

int n, m;
int bo[MAXN];
int p[MAXN][2];
map<int, multiset<int> > mapx, mapy;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        int x, y;
        scanf("%d%d", &x, &y);
        p[i][0] = x;
        p[i][1] = y;
        
        mapx[x].insert(y);
        mapy[y].insert(x);
    }
    for (int i = 1; i <= m; i++){
        int o, n1, n2;
        scanf("%d%d%d", &o, &n1, &n2);
        if (o == 0){
            map<int, multiset<int> >:: iterator it, it1, it2;
            it1 = mapx.lower_bound(n1);
            it2 = mapx.upper_bound(n2);
            
            int cnt = 0;
            for (it = it1; it != it2; it++){
                multiset<int> &myset = (it -> second);
                int x = it -> first;
                cnt +=myset.size();
                for (multiset<int>:: iterator it = myset.begin(); it != myset.end(); it++){
                    int y = *it;
                    mapy[y].erase(x);
                }
            }
            mapx.erase(it1, it2);
            cout << cnt << endl;
        }   else{
            map<int, multiset<int> >:: iterator it, it1, it2;
            it1 = mapy.lower_bound(n1);
            it2 = mapy.upper_bound(n2);
            
            int cnt = 0;
            for (it = it1; it != it2; it++){
                multiset<int> &myset = (it -> second);
                int y = it -> first;
                cnt +=myset.size();
                for (multiset<int>:: iterator it = myset.begin(); it != myset.end(); it++){
                    int x = *it;
                    mapx[x].erase(y);
                }
            }
            mapy.erase(it1, it2);
            cout << cnt << endl;            
        }
    }
    return 0;
}