題意：二維平面上有一堆氣球侮腹，你可以選擇一行x一列y嘲碧，給出一個常數(shù)r。你能獲取到所有橫坐標在x凯旋，x+r，x-r和縱坐標在y钉迷，y+r至非，y-r的所有氣球。求最大的氣球獲取數(shù)糠聪。
題解：先把每個氣球看做九個氣球計算荒椭，這樣轉化為選擇一行和一列，選擇處在這一行和這一列的所有氣球舰蟆。于是：
這樣我們枚舉每一行趣惠，記錄這一行的所有氣球狸棍，這樣來更新哪些列的記錄，從而取得的最大值
用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;
}
