题解 P3415 【祭坛】

· · 题解

先离散化，之后二分答案，对于二分出的答案k，考虑x轴。对于 x = x_0 ，设这一列共有p个柱子，可以建祭坛的地方上方有s个柱子，那么容易发现 min(s, p - s) <= k ，所以对于每一个x，都可以解出一个范围。之后扫描y轴，同样的得到一个范围。对于y轴上的一行，其对答案的贡献即为其范围中有多少个x满足范围，所以边维护x轴的可行性，边统计答案。这里用到单点修改，区间查询，单点查询，线段树维护一下就可以了。复杂度 O(nlog^2n)，得分60 ~ 100分。

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 300005;
const int INF = 1 << 30;
const int BUFMAX = 10000000;
vector<int> x[MAXN];
vector<int> y[MAXN];
int n, q, mx, my;
int u[MAXN], v[MAXN], du[MAXN], dv[MAXN];
int sta[MAXN], ed[MAXN], now[MAXN];
int st[MAXN * 4], id[MAXN];
char BUF[BUFMAX], *buf = BUF;
inline void read(int &n) {
  n = 0;
  while(*buf < '0') buf++;
  while(*buf >= '0') {
    n = n * 10 + *buf - '0'; buf++;
  }
}
void build(int cur, int l, int r) {
  if(l == r) id[l] = cur;
  else {
    int mid = l + r >> 1;
    build(cur << 1, l, mid);
    build(cur << 1 | 1, mid + 1, r);
  }
}
void insert(int cur, int l, int r, int x, int v) {
  st[cur] += v;
  if(l == r) return;
  int mid = l + r >> 1;
  if(x <= mid) insert(cur << 1, l, mid, x, v);
  else insert(cur << 1 | 1, mid + 1, r, x, v);
}
int query(int cur, int l, int r, int a, int b) {
  if(a <= l && b >= r) return st[cur];
  int mid = l + r >> 1;
  if(b <= mid) return query(cur << 1, l, mid, a, b);
  if(a > mid) return query(cur << 1 | 1, mid + 1, r, a, b);
  return query(cur << 1, l, mid, a, b) + query(cur << 1 | 1, mid + 1, r, a, b);
}
inline int query(int x) {
  return st[id[x]];
}
int judge(int k, bool flag = false) {
  memset(st, 0, sizeof(st));
  memset(now, 0, sizeof(now));
  int ans = 0;
  for(int i = 1; i <= mx; i++) {
    int sz = x[i].size();
    if(sz < 2 * k) sta[i] = ed[i] = INF;
    else sta[i] = k; ed[i] = sz - k;
  }
  for(int i = my; i >= 1; i--) {
    int sz = y[i].size();
    int x1 = k, x2 = sz - k;
    if(sz >= 2 * k) {
      x1 = y[i][x1 - 1], x2 = y[i][x2] - 1;
      ans += query(1, 1, mx, x1, x2);
    }
    for(int j = 0; j < sz; j++) {
      int nxtx = y[i][j];
      if(nxtx >= x1 && nxtx <= x2 && query(nxtx) == 1) ans--;
      now[nxtx]++;
      if(now[nxtx] >= sta[nxtx] && now[nxtx] <= ed[nxtx]) {
        if(query(nxtx) == 0) insert(1, 1, mx, nxtx, 1);
      } else if(query(nxtx) == 1) insert(1, 1, mx, nxtx, -1);
    }
    if(flag && ans) return 1;
  }
  return ans;
}
int main() {
  fread(BUF, 1, BUFMAX, stdin);
  read(n);
  for(int i = 1; i <= n; i++) {
    read(u[i]); read(v[i]);
    du[i] = u[i];
    dv[i] = v[i];
  }
  sort(du + 1, du + n + 1);
  sort(dv + 1, dv + n + 1);
  int un = unique(du + 1, du + n + 1) - du - 1;
  int vn = unique(dv + 1, dv + n + 1) - dv - 1;
  for(int i = 1; i <= n; i++) {
    u[i] = lower_bound(du + 1, du + un + 1, u[i]) - du;
    v[i] = lower_bound(dv + 1, dv + vn + 1, v[i]) - dv;
    x[u[i]].push_back(v[i]);
    y[v[i]].push_back(u[i]);
    mx = max(mx, u[i]);
    my = max(my, v[i]);
  }
  for(int i = 1; i <= n; i++) if(y[i].size() >= 2)
    sort(y[i].begin(), y[i].end());
  build(1, 1, mx);
  int l = 1, r = min(mx, my) / 3, ans1, ans2, num;
  while(r - l > 1) {
    int mid = l + r >> 1;
    num = judge(mid, true);
    if(num) l = mid;
    else r = mid;
  }
  num = judge(r);
  if(num) {ans1 = r; ans2 = num;}
  else {ans1 = l; ans2 = judge(l);}
  printf("%d\n", ans1);
  printf("%d\n", ans2);
  return 0;
}