codeforces 1184 C2 曼哈顿距离转切比雪夫距离，矩形覆盖最大点数转最大前缀

题意是给300000个点，点的横坐标和纵坐标范围为[-1e6, 1e6]，找一点A，使得与A的曼哈顿距离 <= r的点数最大，并输出最大点数。

观察可知，与A曼哈顿距离<=r的点构成了一个菱形。注意到菱形的边界的函数为x + y = k和x - y = k，因此想到可以把点(x, y)的坐标变成(x + y, x - y)，从而使得这些点构成一个正方形，正方形的边长为2 * r。注意，这里边长为r的意思是这条边能容纳r+1个格点。

//事实上，在新的坐标系下，切比雪夫距离就是曼哈顿距离。

于是问题转化为找到一个边长为r的正方形，使得被该正方形包含的点的数目最大。

假设某个点在(x, y)处，我们可以把这个点拆成(x + 1, y + 1, 1)，(x - r, y - r, 1)，(x - r, y + 1, -1)，(x + 1, y - r, -1)。第三个维度是权值。

#include <cstdio>
#include <algorithm>

using namespace std;

//(2e6 + 2e6) + 1e6
#define MAXX 5000010
//(2e6 - (-2e6)) + 1e6
#define MAXY 5000010

#define MAXN 300010

const int offsetx = 1000000;
const int offsety = 1000000;
const int offsety2 = 2000000;
const int maxx = MAXX - 5;
const int maxy = MAXY - 5;

struct P {
  int x, y, w;
  bool operator < (const P& rhs) const {
    return x != rhs.x ? x < rhs.x : (y != rhs.y ? y < rhs.y : false);
    //return y != rhs.y ? y < rhs.y : (x != rhs.x ? x < rhs.x : false);
  }
};

#define MAX_NODE_SEGTREE (MAXY << 2)
struct SegTree {
  int maxi[MAX_NODE_SEGTREE], lazy[MAX_NODE_SEGTREE];

  inline int ls(int rt) {
    return rt << 1;
  }
  inline int rs(int rt) {
    return rt << 1 | 1;
  }
  void PushUp(int rt) {
    maxi[rt] = max(maxi[ls(rt)], maxi[rs(rt)]);
  }
  void PushDown(int rt) {
    if (lazy[rt]) {
      lazy[ls(rt)] += lazy[rt];
      lazy[rs(rt)] += lazy[rt];
      maxi[ls(rt)] += lazy[rt];
      maxi[rs(rt)] += lazy[rt];
      lazy[rt] = 0;
    }
  }
  void Add(int rt, int l, int r, int L, int R, int v) {
    if (L <= l && r <= R) {
      lazy[rt] += v;
      maxi[rt] += v;
    } else {
      int mid = (l + r) >> 1;
      PushDown(rt);
      if (L <= mid)
        Add(ls(rt), l, mid, L, R, v);
      if (mid < R)
        Add(rs(rt), mid+1, r, L, R, v);
      PushUp(rt);
    }
  }
  int Max() {
    return maxi[1];
  }
};

int main() {
  int n, r;
  static P points[MAXN * 4];
  static SegTree sgt;

  scanf("%d%d", &n, &r);
  r <<= 1;
  for (int i = 0; i < n; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    x += offsetx;
    y += offsety;
    points[i] = P{r + x + y + 1, r + x - y + offsety2 + 1, 1};
  }
  for (int i = 0; i < n; ++i) {
    points[i+n] = P{points[i].x - r, points[i].y - r, 1};
    points[i+2*n] = P{points[i].x - r, points[i].y + 1, -1};
    points[i+3*n] = P{points[i].x + 1, points[i].y - r, -1};
    ++points[i].x;
    ++points[i].y;
  }
  n <<= 2;
  sort(points, points + n);

  int ans = 0;
  int i = 0;
  while (i < n) {
    int nowx = points[i].x;
    for (; i < n && points[i].x == nowx; ++i) {
      sgt.Add(1, 1, maxy, points[i].y, maxy, points[i].w);
    }
    ans = max(ans, sgt.Max());
  }
  printf("%d", ans);
  
  return 0;
}