牛客第三场 F Popping Balloons —— 思维 + 搞题

题目链接：点我啊╭(╯^╰)╮

题目大意：

    二维平面，$n$ 个气球
    要求水平方向射三枪，垂直射三枪
    每一枪可以打穿一行或一列的所有气球
    水平或垂直的相邻枪的距离为 $r$
    求能射中的最多气球数

解题思路：

    一个气球 $(x,y)$ 在垂直方向上，可以影响到的射击路线是 $y?r,y,y+r$
    在水平方向上，可以被 $x?r,x,x+r$ 影响
    设 $h[x]$ 为射击 $x$ 行可以影响到的所有气球（三行）
    $a[y]$ 为射击 $y$ 列可以影响到的气球数（三列）

    开始将所有气球都加入到每一个 $a[y]$ 中
    枚举每一行 $x$ ，将该行所能射中的所有气球
    所在能被射中的列中删去
    维护每一列的最大射中数
    时间复杂度： $O(3^2\times n\times 2+n\times 3)$

核心：将三行影响转化为一行影响

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
const int maxn = 2e5 + 5;
int n, r, ans, mx, a[maxn], cnt[maxn];
vector <int> h[maxn];inline void add(int y){if(y < 0) return;cnt[a[y]++]--;mx = max(mx, a[y]);cnt[a[y]]++;
}inline void del(int y){if(y < 0) return;cnt[a[y]]--;if(cnt[a[y]]==0 && mx==a[y]) mx--;if(a[y]) cnt[--a[y]]++;
}int main() {scanf("%d%d", &n, &r);for(int i=1, x, y; i<=n; i++){scanf("%d%d", &x, &y);h[x].push_back(y);if(x >= r) h[x-r].push_back(y);h[x+r].push_back(y);add(y), add(y-r), add(y+r);}for(int x=0; x<maxn; x++){int res = h[x].size();if(!res) continue;for(auto y : h[x]) del(y), del(y-r), del(y+r);ans = max(ans, res + mx);for(auto y : h[x]) add(y), add(y-r), add(y+r);}printf("%d\n", ans);
}