ARC065 E - へんなコンパス / Manhattan Compass

問題ページ

解法

まずマンハッタン距離なので45度回転しチェビジェフ距離に変換しておく。
コンパスの移動で穴2つの距離が変わることはない。したがって穴aと穴bの距離Dと等しい穴の組が何個あるのかを考えればよい。穴の組O(N^2)個について全て考えるのは不可能なので穴を一つ固定したときにもう一つの穴になりうる穴の個数について高速に求めたい。これはx(y)座標ごとにy(x)座標を昇順に持っておくと二分探索を用いてO(NlogN)で求められる。コンパスが指すことができる穴のこの値の和 / 2が答えとなる。
あとはコンパスが指すことのできる穴の集合を求めたい。dfsでこれを求める。普通に隣接リストの形で各穴からの遷移先を管理すると削除する対象が多く間に合わない。各穴からの遷移先を個別に持つのではなくx(y)座標ごとにy(x)を昇順に持つsetを使うことにすると削除する対象は一つだけで遷移先は二分探索で求められる。各穴は一回しかアクセスされないのでO(NlogN)でこのdfsは行える。

void dfs(ll v) {
  // vを使用済みに

  for(距離がDの穴u) {
    // uを遷移先から削除
    if(uが使用済みでない) dfs(u);
  }
}

合計でO(NlogN)で答えを求めることができる。

遷移先をうまく管理すると各頂点一回しか訪れないのでO(N)でdfsができる。こういう実装が苦手…

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n, a, b;
  cin >> n >> a >> b;
  a--, b--;
  vector<ll> x(n), y(n);
  map<ll, vector<ll>> xy_v, yx_v;
  map<ll, set<PII>> xy_s, yx_s;
  REP(i, n) {
    ll xx, yy; cin >> xx >> yy;
    x[i] = xx - yy;
    y[i] = xx + yy;
    xy_v[x[i]].push_back(y[i]);
    yx_v[y[i]].push_back(x[i]);
    xy_s[x[i]].insert({y[i], i});
    yx_s[y[i]].insert({x[i], i});
  }

  vector<bool> used(n);
  ll dist = max(abs(x[a]-x[b]), abs(y[a]-y[b]));
  function<void(ll)> dfs = [&](ll v) {
    used[v] = true;

    // 左
    while(1) {
      auto itr = xy_s[x[v]-dist].lower_bound({y[v]-dist, -1});
      if(itr == xy_s[x[v]-dist].end() || itr->first > y[v]+dist) break;
      xy_s[x[v] - dist].erase(itr);
      if(!used[itr->second]) dfs(itr->second);
    }
    // 右
    while(1) {
      auto itr = xy_s[x[v]+dist].lower_bound({y[v]-dist, -1});
      if(itr == xy_s[x[v]+dist].end() || itr->first > y[v]+dist) break;
      xy_s[x[v]+dist].erase(itr);
      if(!used[itr->second]) dfs(itr->second);
    }
    // 下
    while(1) {
      auto itr = yx_s[y[v]-dist].lower_bound({x[v]-dist, -1});
      if(itr == yx_s[y[v]-dist].end() || itr->first > x[v]+dist) break;
      yx_s[y[v]-dist].erase(itr);
      if(!used[itr->second]) dfs(itr->second);
    }
    // 上
    while(1) {
      auto itr = yx_s[y[v]+dist].lower_bound({x[v]-dist, -1});
      if(itr == yx_s[y[v]+dist].end() || itr->first > x[v]+dist) break;
      yx_s[y[v]+dist].erase(itr);
      if(!used[itr->second]) dfs(itr->second);
    }
  };
  dfs(a);

  for(auto &itr: xy_v) sort(ALL(itr.second));
  for(auto &itr: yx_v) sort(ALL(itr.second));
  ll ret = 0;
  REP(i, n) {
    if(!used[i]) continue;
    ret += upper_bound(ALL(xy_v[x[i]-dist]), y[i]+dist)
      - lower_bound(ALL(xy_v[x[i]-dist]), y[i]-dist);
    ret += upper_bound(ALL(xy_v[x[i]+dist]), y[i]+dist)
      - lower_bound(ALL(xy_v[x[i]+dist]), y[i]-dist);
    ret += lower_bound(ALL(yx_v[y[i]-dist]), x[i]+dist)
      - upper_bound(ALL(yx_v[y[i]-dist]), x[i]-dist);
    ret += lower_bound(ALL(yx_v[y[i]+dist]), x[i]+dist)
      - upper_bound(ALL(yx_v[y[i]+dist]), x[i]-dist);
  }
  cout << ret/2 << endl;

  return 0;
}