题意：一个无限大的棋盘， 有n个小兵， 给出了n个兵的坐标， 现在有一个长为w高为h的炸弹放在棋盘上， 炸弹只能上下左右平移， 不能旋转，且放炸弹的区域不能含有士兵， 炸弹可以一次炸掉与它同一行同一列的所有士兵。 放一颗炸弹， 问最多能炸死多少士兵
解题思路：坐标离散化后可以计算出水平方向和竖直方向上所有长度为w和h区间内士兵的个数，线段树维护水平方向长度为w区间内士兵个数的最大值，枚举每个竖直方向长度为h的区间，每次在将竖直方向长度为h的区间内的点，在线段树上对应长为w的区间减去n，之后若该点不在这个竖直方向长度为h的区间内，那么在线段树上对应长为w的区间加上n
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; int a[200009 << 2], lazy[200009 << 2]; int x[200009], y[200009]; int xx[200009], yy[200009], cnt1, cnt2; int sumx[200009], sumy[200009]; vector <int> g1[200009], g2[200009]; int n, w, h; void build(int k, int l, int r) { lazy[k] = 0; if (l == r) { a[k] = sumx[l]; return; } int mid = (l + r) >> 1; build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r); a[k] = max(a[k << 1], a[k << 1 | 1]); } void Push(int k) { a[k << 1] += lazy[k], a[k << 1 | 1] += lazy[k]; lazy[k << 1] += lazy[k], lazy[k << 1 | 1] += lazy[k]; lazy[k] = 0; } void update(int k, int l, int r, int ll, int rr, int val) { if (ll <= l && rr >= r) { a[k] += val, lazy[k] += val; return; } if (lazy[k]) Push(k); int mid = (l + r) >> 1; if (ll <= mid) update(k << 1, l, mid, ll, rr, val); if (rr > mid) update(k << 1 | 1, mid + 1, r, ll, rr, val); a[k] = max(a[k << 1], a[k << 1 | 1]); } int main() { int t, cas = 1; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &w, &h); cnt1 = cnt2 = 1; memset(sumx, 0, sizeof sumx); memset(sumy, 0, sizeof sumy); for (int i = 0; i < 200005; i++) { g1[i].clear(); g2[i].clear(); } for (int i = 0; i < n; i++) { scanf("%d%d", &x[i], &y[i]); xx[cnt1++] = x[i]; xx[cnt1++] = x[i] - w + 1; yy[cnt2++] = y[i]; yy[cnt2++] = y[i] - h + 1; } sort(xx + 1, xx + cnt1); sort(yy + 1, yy + cnt2); cnt1 = unique(xx + 1, xx + cnt1) - xx; cnt2 = unique(yy + 1, yy + cnt2) - yy; for (int i = 0; i < n; i++) { int x1 = lower_bound(xx + 1, xx + cnt1, x[i] - w + 1) - xx; int x2 = lower_bound(xx + 1, xx + cnt1, x[i]) - xx; int y1 = lower_bound(yy + 1, yy + cnt2, y[i] - h + 1) - yy; int y2 = lower_bound(yy + 1, yy + cnt2, y[i]) - yy; sumx[x1]++; sumx[x2 + 1]--; sumy[y1]++; sumy[y2 + 1]--; g1[y1].push_back(i); g2[y2].push_back(i); } int ans = 0; for (int i = 1; i <= cnt1; i++) sumx[i] += sumx[i - 1], ans = max(ans, sumx[i]); for (int i = 1; i <= cnt2; i++) sumy[i] += sumy[i - 1], ans = max(ans, sumy[i]); build(1, 1, cnt1); for (int i = 1; i <= cnt2; i++) { for (int j = 0; j < g1[i].size(); j++) { int x1 = lower_bound(xx + 1, xx + cnt1, x[g1[i][j]]) - xx; int y1 = lower_bound(xx + 1, xx + cnt1, x[g1[i][j]] - w + 1) - xx; update(1, 1, cnt1, y1, x1, -n); } int res = a[1]; if (res > 0) ans = max(ans, sumy[i] + res); for (int j = 0; j < g2[i].size(); j++) { int x1 = lower_bound(xx + 1, xx + cnt1, x[g2[i][j]]) - xx; int y1 = lower_bound(xx + 1, xx + cnt1, x[g2[i][j]] - w + 1) - xx; update(1, 1, cnt1, y1, x1, n); } } printf("Case #%d: %d\n", cas++, ans); } return 0; }
