問題
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
を作る。
クエリ処理
例として,スタート地点からの距離が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は大きくなるので,座標圧縮する必要がある。