AtCoder Regular Contest 060: E - 高橋君とホテル / Tak and Hotels
見れば分かった。東京大学プログラミングコンテスト2012: H - 区間スケジューリングクエリを直前に解いていたため。
solution
doubling。前処理$O(N \log N)$ クエリ$O(Q \log N)$。
愚直解としては、進めるところまで貪欲に進むことを繰り返せばよい。 このときあるホテルを出発して次に泊まるホテルは一意に定まる。 これを事前に求めておきdoublingを用いればクエリあたり$O(\log N)$となる。
implementation
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define ALL(x) begin(x), end(x)
using namespace std;
template <typename UnaryPredicate>
int64_t binsearch_max(int64_t l, int64_t r, UnaryPredicate p) {
assert (l <= r);
++ r;
while (r - l > 1) {
int64_t m = l + (r - l) / 2; // avoid overflow
(p(m) ? l : r) = m;
}
return l;
}
struct doubling_table {
vector<vector<int> > table;
doubling_table() = default;
doubling_table(vector<int> const & next, int size = -1) {
int n = next.size();
{
auto it = minmax_element(ALL(next));
assert (0 <= *(it.first) and *(it.second) <= n);
}
if (size == -1) {
size = max<int>(1, ceil(log2(n)));
}
table.resize(size);
table[0] = next;
REP (k, size - 1) {
table[k + 1].resize(n, n);
REP (i, n) if (table[k][i] != n) {
table[k + 1][i] = table[k][table[k][i]];
}
}
}
};
int main() {
// input
int n; scanf("%d", &n);
vector<int> a(n); REP (i, n) scanf("%d", &a[i]);
int l; scanf("%d", &l);
// prepare
vector<int> next(n);
REP (i, n) {
next[i] = binsearch_max(i, n - 1, [&](int j) {
return a[j] - a[i] <= l;
});
}
doubling_table doubling(next);
// serve
int queries; scanf("%d", &queries);
while (queries --) {
int a, b; scanf("%d%d", &a, &b);
-- a; -- b;
if (a > b) swap(a, b);
int result = 0;
REP_R (k, doubling.table.size()) {
if (doubling.table[k][a] < b) {
a = doubling.table[k][a];
result += 1 << k;
}
}
while (a < b) {
a = next[a];
result += 1;
}
// output
printf("%d\n", result);
}
return 0;
}