ARC063_F すぬけ君の塗り絵 2

うくなので

atcoder.jp

解法

求めたいものは, 内部に点を含まない最大周長の長方形.

特に の周長は答えの下界. ここで長方形が または を通らないと仮定すると周長は最大でも となり下界を下回るため矛盾. 従って長方形とどちらかの直線は共通部分を持つことが仮定できる.

以下 と共通部分を持つとする. の場合も同様の問題を解けば良い.

で, 結論なんですがこういうのは分割統治をすると解ける. まず点を の昇順でソートしておく. 次にある(点の)区間 内でなる長方形を考える.

この区間の中心 と長方形が共通部分を持たない場合については, 中心で左右に分割して再帰的に解けば良い.

中心 と共通部分を持つ場合について考える. 以下のように4つの領域 に分ける.

それぞれの領域で塗りつぶす方向はそれぞれに定まって例えば では←か↑, では→か↑といった感じになる.

また領域 で←に割り当てる最も右側にある点を決め打つと、自動的に以下のように定まる. の↑や の↓はその区間で出現した 座標の最小値/最大値である.

同様に についても→に割り当てる最も左側にある点を決め打つことで、匚とコをマッチングさせて最大長を求める問題に帰着される.

匚とコを総当たりして最大値を求めると破滅的に遅いんですが, これは書いてみると高速化できる見た目をしていて, 匚とコの上側のーの座標でソートしておくことで実家高速化が可能. 座圧してセグ木を使ってRMQを求める問題に帰着される.

コード

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const int64 infll = (1LL << 61) - 1;

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

using pi = pair< int, int >;

int W, H, N, L;
vector< pi > P;

template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;

  int sz;
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = f(seg[k], x);
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }
};

auto f = [](int a, int b) { return max(a, b); };

int rec(int l, int r) {
  if(l + 1 >= r) return 0;
  int mid = (l + r) / 2;
  int ret = max(rec(l, mid), rec(mid, r));


  int UY = 0, DY = H;
  vector< pair< pi, pi > > ask;
  vector< int > xs;
  for(int i = mid - 1; i >= l; i--) {
    xs.emplace_back(DY);
    ask.emplace_back(pi(P[i].first, 0), pi(UY, DY));
    if(P[i].second < L) chmax(UY, P[i].second);
    else chmin(DY, P[i].second);
  }
  UY = 0, DY = H;
  for(int i = mid; i < r; i++) {
    xs.emplace_back(DY);
    ask.emplace_back(pi(P[i].first, 1), pi(UY, DY));
    if(P[i].second < L) chmax(UY, P[i].second);
    else chmin(DY, P[i].second);
  }

  sort(ask.begin(), ask.end(), [&](auto p, auto q) {
    return p.second.first < q.second.first;
  });
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));

  {
    SegmentTree< int > seg1(xs.size(), f, -inf), seg2(xs.size(), f, -inf);
    for(auto &p : ask) {
      int pos = lower_bound(begin(xs), end(xs), p.second.second) - begin(xs);
      int64 subret = -infll;
      if(p.first.second) {
        chmax(subret, seg1.query(pos, xs.size()) + p.second.second);
        chmax(subret, seg2.query(0, pos));
        chmax(ret, subret + p.first.first - p.second.first);
      } else {
        seg1.update(pos, -p.first.first);
        seg2.update(pos, -p.first.first + p.second.second);
      }
    }
  }

  {
    SegmentTree< int > seg1(xs.size(), f, -inf), seg2(xs.size(), f, -inf);
    for(auto &p : ask) {
      int pos = lower_bound(begin(xs), end(xs), p.second.second) - begin(xs);
      int64 subret = -infll;
      if(p.first.second) {
        seg1.update(pos, p.first.first);
        seg2.update(pos, p.first.first + p.second.second);
      } else {
        chmax(subret, seg1.query(pos, xs.size()) + p.second.second);
        chmax(subret, seg2.query(0, pos));
        chmax(ret, subret - p.first.first - p.second.first);
      }
    }
  }


  return ret;
}

int main() {
  cin >> W >> H >> N;
  P.resize(N);
  for(auto &p : P) {
    cin >> p.first >> p.second;
  }
  P.emplace_back(0, 0);
  P.emplace_back(W, H);
  sort(begin(P), end(P));
  P.erase(unique(begin(P), end(P)), end(P));
  N = (int) P.size();
  L = H / 2;
  int ret = rec(0, N);
  swap(W, H);
  for(auto &p : P) swap(p.first, p.second);
  sort(begin(P), end(P));
  L = H / 2;
  cout << max(ret, rec(0, N)) * 2 << endl;
}