AOJ 1505 Dungeon

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1505&lang=jp

前処理

とりあえずスタート地点からの最短距離d_s,ゴール地点からの最短距離d_gを計算する。

たとえば,各頂点のd_s,d_gが以下のような感じだったとする。

d_s d_g
0 5
1 1
1 2
1 4
3 1
3 3

以下のようなvector<vector<int>> Xを作る。

f:id:kujira16:20150822231247p:plain

クエリ処理

例として,スタート地点からの距離が2以下,ゴール地点からの距離が4以上の頂点を数えることを考える。

vector<vector<int>> Xの中身のvector<int>を予めソートしておけば,答えを計算する時に二分探索が使える。

int ans = 0;
ans += X[0].end() - lower_bound(X[0].begin(), X[0].end(), 4);
ans += X[1].end() - lower_bound(X[1].begin(), X[1].end(), 4);
ans += X[2].end() - lower_bound(X[2].begin(), X[2].end(), 4);
return ans;

これでもまだ遅いので,vector<vector<int>> Xの持ち方を,ソート済みのvector<int>を要素に持つセグメントツリー,BIT,平方分割などに変える。

また,スタート地点からの最短距離d_sとゴール地点からの最短距離d_gは大きくなるので,座標圧縮する必要がある。