#include "jumps.h" #include <vector> using namespace std; const int N = 200000; typedef vector<int> vi; int max(int a, int b) { return a > b ? a : b; } int ll[N], rr[N], qu[N], n, special; int dd[N], pp[N], pp_[N], dd_[N], qq[N], qq_[N]; void dfs(int *dd, int *pp, int *pp_, int i) { if (dd[i]) return; if (pp[i] == -1) dd[i] = 1, pp_[i] = -1; else { int p, p_; dfs(dd, pp, pp_, pp[i]); p = pp[i], p_ = pp_[p]; dd[i] = dd[p] + 1, pp_[i] = dd[p] - dd[pp_[p]] != dd[p_] - dd[pp_[p_]] ? p : pp_[p_]; } } void init(int n_, vi aa) { int i, cnt; n = n_; special = 1; for (i = 0; i < n; i++) if (aa[i] != i + 1) { special = 0; break; } cnt = 0; for (i = 0; i < n; i++) { while (cnt && aa[qu[cnt - 1]] < aa[i]) cnt--; ll[i] = cnt == 0 ? -1 : qu[cnt - 1]; qu[cnt++] = i; } cnt = 0; for (i = n - 1; i >= 0; i--) { while (cnt && aa[qu[cnt - 1]] < aa[i]) cnt--; rr[i] = cnt == 0 ? -1 : qu[cnt - 1]; qu[cnt++] = i; } for (i = 0; i < n; i++) { pp[i] = ll[i] == -1 || rr[i] == -1 ? (ll[i] == -1 ? rr[i] : ll[i]) : (aa[ll[i]] < aa[rr[i]] ? ll[i] : rr[i]); qq[i] = ll[i] == -1 || rr[i] == -1 ? (ll[i] == -1 ? rr[i] : ll[i]) : (aa[ll[i]] > aa[rr[i]] ? ll[i] : rr[i]); } for (i = 0; i < n; i++) dfs(dd, pp, pp_, i), dfs(dd_, qq, qq_, i); } int query(int i, int j) { int cnt = 0; while (1) if (qq_[i] != -1 && dd[qq_[i]] >= dd[j]) cnt += dd_[i] - dd_[qq_[i]], i = qq_[i]; else if (qq[i] != -1 && dd[qq[i]] >= dd[j]) cnt++, i = qq[i]; else break; while (1) if (pp_[i] != -1 && dd[pp_[i]] >= dd[j]) cnt += dd[i] - dd[pp_[i]], i = pp_[i]; else if (pp[i] != -1 && dd[pp[i]] >= dd[j]) cnt++, i = pp[i]; else break; return i == j ? cnt : -1; } int dd1[N]; int minimum_jumps(int i1, int j1, int i2, int j2) { if (special) return i2 - j1; else if (i1 == j1 && i2 == j2) return query(i1, i2); else { int head, cnt, i; for (i = 0; i < n; i++) dd1[i] = n; head = cnt = 0; for (i = i1; i <= j1; i++) dd1[i] = 0, qu[head + cnt++] = i; while (cnt) { int d; i = qu[cnt--, head++], d = dd1[i] + 1; if (i2 <= i && i <= j2) return dd1[i]; if (ll[i] != -1 && dd1[ll[i]] > d) dd1[ll[i]] = d, qu[head + cnt++] = ll[i]; if (rr[i] != -1 && dd1[rr[i]] > d) dd1[rr[i]] = d, qu[head + cnt++] = rr[i]; } return -1; } }