题意：一个无限大的棋盘， 有n个小兵， 给出了n个兵的坐标， 现在有一个长为width 高为height的炸弹放在棋盘上， 炸弹只能上下左右平移， 不能旋转。
且放炸弹的区域不能含有士兵， 炸弹可以一次炸掉与它同一行同一列的所有士兵。 放一颗炸弹， 使得炸死的士兵最多。输出最大值。
思路：先不考虑离散化， 可以计算出水平方向和竖直方向上所有长度为width和height区间内士兵的个数， 得到一个数组prefixX， prefixY。
然后一次遍历prefixY数组， 假设区间[i, i+height-1]对应prefixY[i]， 而且[i, i+height-1]内所有士兵的x坐标对应的prefixX都减去一个大于n的数字MAX（这样保证炸弹不会放在士兵上），这个时候求prefixX上的一个最大值max再加上prefixY[i]就可以更新答案result了， 如果max是一个负数那么说明当前这个区间不能放炸弹。 之后再把第i行的所有士兵的x坐标对应的prefixX都加上MAX。 这样一次下去就可以了。线段树区间操作。
还有一个需要特判的地方是 上面并没有找到一个可以放炸弹的地方。 这个时候答案就是prefixX和prefixY的最大值。
思路一下子就想出来了，可是怎么离散化想了好久。。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + ;
struct SegTree{
int seg[maxn << ], lazy[maxn << ];
void build(int l, int r, int pos, int val[]){
lazy[pos] = ;
if (l == r){
seg[pos] = val[l];
return;
}
int mid = (l + r) >> ;
build(l, mid, pos<<, val);
build(mid+, r, pos<<|, val);
seg[pos] = max(seg[pos<<], seg[pos<<|]);
}
void push_down(int pos){
if (lazy[pos]){
seg[pos<<] += lazy[pos];
seg[pos<<|] += lazy[pos];
lazy[pos<<] += lazy[pos];
lazy[pos<<|] += lazy[pos];
lazy[pos] = ;
}
}
void update (int l, int r, int pos, int ua, int ub, int val){
if (ua > ub){
return;
}
if (ua <= l && ub >= r){
seg[pos] += val;
lazy[pos] += val;
return;
}
push_down(pos);
int mid = (l + r) >> ;
if (ua <= mid){
update(l, mid, pos<<, ua, ub, val);
}
if (ub > mid){
update(mid+, r, pos<<|, ua, ub, val);
}
seg[pos] = max(seg[pos<<], seg[pos<<|]);
}
}tree;
int pawX[maxn], pawY[maxn];
int lshX[maxn], lshY[maxn], tot1, tot2;
int prefixX[maxn], prefixY[maxn], valX[maxn], valY[maxn];
vector <int> vec1[maxn], vec2[maxn];
void init(){
memset(prefixX, , sizeof prefixX);
memset(prefixY, , sizeof prefixY);
for (int i = ; i < maxn; i++){
vec1[i].clear();
vec2[i].clear();
}
}
int main(){
int T, cas = ;
scanf ("%d", &T);
while (T--){
int n, width, height;
scanf ("%d%d%d", &n, &width, &height);
tot1 = tot2 = ;
init();
for (int i = ; i < n; i++){
int x, y;
scanf ("%d%d", &x, &y);
pawX[i] = x, pawY[i] = y;
lshX[tot1++] = x;
lshX[tot1++] = x - width+;
lshY[tot2++] = y;
lshY[tot2++] = y-height+;
}
sort(lshX, lshX+tot1);
sort(lshY, lshY+tot2);
tot1 = unique(lshX, lshX+tot1) - lshX;
tot2 = unique(lshY, lshY+tot2) - lshY;
for (int i = ; i < n; i++){
int x1 = lower_bound(lshX, lshX+tot1, pawX[i]-width+) - lshX + ;
int x2 = lower_bound(lshX, lshX+tot1, pawX[i]) - lshX + ;
int y1 = lower_bound(lshY, lshY+tot2, pawY[i]-height+) - lshY + ;
int y2 = lower_bound(lshY, lshY+tot2, pawY[i]) - lshY + ;
prefixX[x1]++; prefixX[x2+]--;
prefixY[y1]++; prefixY[y2+]--;
vec1[y1].push_back(i);
vec2[y2].push_back(i);
}
int res = ;
for (int i = ; i <= tot1; i++){
prefixX[i] += prefixX[i-];
res = max(res, prefixX[i]); // 这里要特判一下
}
for (int i = ; i <= tot2; i++){
prefixY[i] += prefixY[i-];
res = max(res, prefixY[i]); // 这里要特判一下
}
tree.build(, tot1, , prefixX);
const int tenThousand = 1e5;
for (int i = ; i <= tot2; i++){
for (int j = ; j < vec1[i].size(); j++){
int idx = vec1[i][j];
int x = lower_bound(lshX, lshX+tot1, pawX[vec1[i][j]]) - lshX + ;
int y = lower_bound(lshX, lshX+tot1, pawX[vec1[i][j]]-width+) - lshX + ;
tree.update(, tot1, , y, x, -tenThousand);
}
int ret = tree.seg[];
if (ret > )
res = max(res, prefixY[i]+ret);
for (int j = ; j < vec2[i].size(); j++){
int x = lower_bound(lshX, lshX+tot1, pawX[vec2[i][j]]) - lshX + ;
int y = lower_bound(lshX, lshX+tot1, pawX[vec2[i][j]]-width+) - lshX + ;
tree.update(, tot1, , y, x, tenThousand);
}
}
printf("Case #%d: %d\n", cas++, res);
}
return ;
}