#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back
/*
yeah i could've used a set... but
i'm just coding a segtree because vibes :D
*/
struct Tree {
Tree *lt, *rt;
int l, r;
int mn1, mx1;
Tree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), mn1(INF(int)), mx1(NINF(int)) {};
void combine() {
mn1 = min(lt->mn1, rt->mn1);
mx1 = max(lt->mx1, rt->mx1);
}
void build(const vb& a) {
if(l == r) {
if(a[l]) {
mn1 = mx1 = l;
}
return;
}
int m = (l + r) >> 1;
lt = new Tree(l, m);
rt = new Tree(m + 1, r);
lt->build(a);
rt->build(a);
combine();
}
int qmin(int ql, int qr) {
if(ql > r || qr < l) return INF(int);
if(ql == l && qr == r) return mn1;
int m = (l + r) >> 1;
return min(lt->qmin(ql, min(qr, m)), rt->qmin(max(ql, m + 1), qr));
}
int qmax(int ql, int qr) {
if(ql > r || qr < l) return NINF(int);
if(ql == l && qr == r) return mx1;
int m = (l + r) >> 1;
return max(lt->qmax(ql, min(qr, m)), rt->qmax(max(ql, m + 1), qr));
}
void upd(int i, bool nv) {
if(l == r) {
if(nv) mn1 = mx1 = l;
else {
mn1 = INF(int);
mx1 = NINF(int);
}
return;
}
int m = (l + r) >> 1;
if(i <= m) lt->upd(i, nv);
else rt->upd(i, nv);
combine();
}
};
struct MaxTree {
MaxTree *lt, *rt;
int l, r, v;
MaxTree(int a_l, int a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(NINF(int)) {};
void combine() {
v = max(lt->v, rt->v);
}
void build(const vi& a) {
if(l == r) {
v = a[l];
return;
}
int m = (l + r) >> 1;
lt = new MaxTree(l, m);
rt = new MaxTree(m + 1, r);
lt->build(a);
rt->build(a);
combine();
}
int qry(int ql, int qr) {
if(ql > r || qr < l) return NINF(int);
if(ql == l && qr == r) return v;
int m = (l + r) >> 1;
return max(lt->qry(ql, min(qr, m)), rt->qry(max(ql, m + 1), qr));
}
};
vi g_lptr;
vi g_rptr;
void print_vec(const vi& v) {
for(int vv : v) cerr << vv << " ";
cerr << endl;
}
struct PICK_STRATEGY {
const static int HEAVY = 0, LIGHT = 1, LEFT = 2, RIGHT = 3;
};
const int MAX_JUMP = 20;
vvi compute_jump_pointers(const vi& lptr, const vi& rptr, const vpi& node_order, const vi& h, int strategy) {
int n = lptr.size();
vvi jump(n, vi(MAX_JUMP, -1));
// Initialize jump pointers
for(int i = 0; i < n; i++) {
int next_ptr = -1;
switch(strategy) {
default:
case PICK_STRATEGY::HEAVY:
{
if(lptr[i] == NINF(int)) {
next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]);
} else if(rptr[i] == INF(int)) {
next_ptr = lptr[i];
} else if(h[lptr[i]] > h[rptr[i]]) {
next_ptr = lptr[i];
} else {
next_ptr = rptr[i];
}
}
break;
case PICK_STRATEGY::LIGHT:
{
if(lptr[i] == NINF(int)) {
next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]);
} else if(rptr[i] == INF(int)) {
next_ptr = lptr[i];
} else if(h[lptr[i]] > h[rptr[i]]) {
next_ptr = rptr[i];
} else {
next_ptr = lptr[i];
}
}
break;
case PICK_STRATEGY::LEFT:
{
next_ptr = (lptr[i] == NINF(int) ? -1 : lptr[i]);
}
break;
case PICK_STRATEGY::RIGHT:
{
next_ptr = (rptr[i] == INF(int) ? -1 : rptr[i]);
}
break;
}
jump[i][0] = next_ptr;
}
for(int i = 0; i < n; i++) {
int ci = node_order[i].second;
for(int j = 1; j < MAX_JUMP; j++) {
if(jump[ci][j - 1] == -1) break;
jump[ci][j] = jump[jump[ci][j - 1]][j - 1];
}
}
return jump;
}
vvi heavy_ptrs;
vvi left_ptrs;
vvi right_ptrs;
MaxTree* g_tr;
vi g_h;
void init(int N, vi H) {
// computing left/right pointers
vpi h_ind_pairs_right_order;
vpi h_ind_pairs_left_order;
vi lptr(N, -1);
vi rptr(N, -1);
for(int i = 0 ; i < N; i++) {
h_ind_pairs_right_order.pb({H[i], i});
h_ind_pairs_left_order.pb({H[i], i});
}
sort(h_ind_pairs_right_order.begin(), h_ind_pairs_right_order.end(), [](pi a, pi b) {return a.first > b.first || (a.first == b.first && a.second < b.second);});
sort(h_ind_pairs_left_order.begin(), h_ind_pairs_left_order.end(), [](pi a, pi b) {return a.first > b.first || (a.first == b.first && a.second > b.second);});
Tree* tr_right = new Tree(0, N - 1);
Tree* tr_left = new Tree(0, N - 1);
vb all_false(N, false);
tr_right->build(all_false);
tr_left->build(all_false);
for(int i = 0 ; i < N; i++) {
rptr[h_ind_pairs_right_order[i].second] = tr_right->qmin(h_ind_pairs_right_order[i].second + 1, N - 1);
lptr[h_ind_pairs_left_order[i].second] = tr_left->qmax(0, h_ind_pairs_left_order[i].second - 1);
tr_right->upd(h_ind_pairs_right_order[i].second, true);
tr_left->upd(h_ind_pairs_left_order[i].second, true);
}
g_lptr = lptr;
g_rptr = rptr;
/*
computing jump pointers
you will need:
(1) heavy jump pointers
(2) light jump pointers (nvm no need for this)
(3) left jump pointers
(4) right jump pointers
*/
heavy_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::HEAVY);
left_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::LEFT);
right_ptrs = compute_jump_pointers(lptr, rptr, h_ind_pairs_left_order, H, PICK_STRATEGY::RIGHT);
g_tr = new MaxTree(0, N - 1);
g_tr->build(H);
g_h = H;
}
int p2p_minjumps(int s, int e) {
if(g_tr->qry(s, e - 1) >= g_h[e]) return -1;
int num_jumps = 0;
int ci = s;
// Jump along heavy edges
for(int i = MAX_JUMP - 1; i >= 0; i--) {
if(heavy_ptrs[ci][i] != -1 && g_h[heavy_ptrs[ci][i]] < g_h[e]) {
// if we can jump, jump
num_jumps |= 1 << i;
ci = heavy_ptrs[ci][i];
}
}
// Jump to the right
for(int i = MAX_JUMP - 1; i >= 0; i--) {
if(right_ptrs[ci][i] != -1 && right_ptrs[ci][i] <= e) {
// if we can jump, jump
num_jumps += 1 << i;
ci = right_ptrs[ci][i];
}
}
return num_jumps;
}
int minimum_jumps(int A, int B, int C, int D) {
// Binary jumping
// The idea is to find the optimal starting point in [A, B]
// Move as far to the right as you possibly can (find the peak)
int max_end = C;
for(int i = MAX_JUMP - 1; i >= 0; i--) {
if(right_ptrs[max_end][i] != -1 && right_ptrs[max_end][i] <= D) {
max_end = right_ptrs[max_end][i];
}
}
if(g_tr->qry(B, max_end - 1) >= g_h[max_end]) return -1;
// Move as far to the left as you possibly can
int cs = B;
for(int i = MAX_JUMP - 1; i >= 0; i--) {
if(left_ptrs[cs][i] != -1 && g_h[left_ptrs[cs][i]] < g_h[max_end] && left_ptrs[cs][i] >= A) {
cs = left_ptrs[cs][i];
}
}
// Move as far to the right as you can from the optimal starting point
int ce = cs;
for(int i = MAX_JUMP - 1; i >= 0; i--) {
if(right_ptrs[ce][i] != -1 && right_ptrs[ce][i] < C) {
ce = right_ptrs[ce][i];
}
}
ce = right_ptrs[ce][0];
// Now, keep going left and check how many moves it would take to exceed that
int moves_to_left = 0;
int cl = cs;
for(int i = MAX_JUMP - 1; i >= 0; i--) {
if(left_ptrs[cl][i] != -1 && g_h[left_ptrs[cl][i]] <= g_h[ce]) {
cl = left_ptrs[cl][i];
moves_to_left += 1 << i;
}
}
// One more jump
cl = left_ptrs[cl][0];
moves_to_left ++;
bool left_jump_valid = (cl >= 0 && g_h[cl] < g_h[max_end]); // in plain english, valid siya if you can jump to the right tapos cl is a valid index
return (left_jump_valid ? min(p2p_minjumps(cs, ce), moves_to_left + 1) : p2p_minjumps(cs, ce));
}
