2019牛客第九场F题（Popping Balloons）贪心 + multiset / 线段树

题意：二维平面上有一堆气球，你可以选择一行x一列y，给出一个常数r。你能获取到所有横坐标在x，x+r，x-r和纵坐标在y，y+r，y-r的所有气球。求最大的气球获取数。

题解：先把每个气球看做九个气球计算，这样转化为选择一行和一列，选择处在这一行和这一列的所有气球。于是：

这样我们枚举每一行，记录这一行的所有气球，这样来更新哪些列的记录，从而取得的最大值

用multiset或者单点更新线段树来做这件事就行了，注意multiset的erase key会把所有等于key的值都给搞掉，如果要删除一个元素的话应该应该先find找到iterator再erase

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define int long long
using namespace std;
using pii = pair<int, int>;
const int maxn = 3e5 + 10;
int sumr[maxn], sumc[maxn];
vector<pii> vec[maxn];
int32_t main()
{
    ios::sync_with_stdio(false);
    map<pii, int> a;
    int n, r;
    cin >> n >> r;
    while (n--)
    {
        int x, y;
        cin >> x >> y;
        for (int i = x; i <= x + 2 * r; i += r)
        {
            sumr[i]++;
        }
        for (int j = y; j <= y + 2 * r; j += r)
        {
            sumc[j]++;
        }
        for (int i = x; i <= x + 2 * r; i += r)
            for (int j = y; j <= y + 2 * r; j += r)
                a[make_pair(i, j)]++;
    }
    for (auto &p : a)
    {
        vec[p.first.first].emplace_back(p.first.second, p.second);
    }
    multiset<int> seg;
    for (int i = 0; i < maxn; i++)
    {
        if (sumc[i])
            seg.insert(sumc[i]);
    }
    int ans = 0;
    for (int i = 0; i < maxn; i++)
    {
        for (auto &p : vec[i])
        {
            int j = p.first;
            int val = p.second;
            auto it = seg.find(sumc[j]);
            seg.erase(it);
            seg.insert(sumc[j] - val);
        }
        int left = *seg.rbegin();
        ans = max(ans, sumr[i] + left);
        for (auto &p : vec[i])
        {
            int j = p.first;
            int val = p.second;
            auto it = seg.find(sumc[j] - val);
            seg.erase(it);
            seg.insert(sumc[j]);
        }
    }
    cout << ans << endl;
}