fn main() {
    let mut jump1: Vec<i32> = vec![2, 5, 1, 1, 1, 1];
    let mut jump2 = jump1.clone();
    let ans1 = min_jump(&mut jump1);
    let ans2 = min_jump2(&mut jump2);
    println!("ans1 = {}", ans1);
    println!("ans2 = {}", ans2);
}

// 宽度优先遍历
// N*logN
fn min_jump(jump: &mut Vec<i32>) -> i32 {
    let n = jump.len() as i32;
    let mut queue: Vec<i32> = vec![];
    for _ in 0..n {
        queue.push(0);
    }
    let mut l: i32 = 0;
    let mut r: i32 = 0;
    queue[r as usize] = 0;
    r += 1;
    let mut it = IndexTree::new(n);
    // 1...n初始化的时候 每个位置填上1
    for i in 1..n {
        it.add(i, 1);
    }
    let mut step: i32 = 0;
    while l != r {
        // 队列里面还有东西
        // tmp记录了当前层的终止位置！
        let tmp = r;
        // 当前层的所有节点，都去遍历!
        while l < tmp {
            let cur = queue[l as usize];
            let forward = cur + jump[cur as usize];
            if forward >= n {
                return step + 1;
            }
            if it.value(forward) != 0 {
                queue[r as usize] = forward;
                r += 1;
                it.add(forward, -1);
            }
            // cur
            // 1....cur-1 cur
            while it.sum(cur - 1) != 0 {
                let find0 = find(&mut it, cur - 1);
                it.add(find0, -1);
                queue[r as usize] = find0;
                r += 1;
            }
            l += 1;
        }
        step += 1;
    }
    return -1;
}

fn find(it: &mut IndexTree, mut right: i32) -> i32 {
    let mut left = 0;
    let mut mid;
    let mut find0 = 0;
    while left <= right {
        mid = (left + right) / 2;
        if it.sum(mid) > 0 {
            find0 = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return find0;
}

pub struct IndexTree {
    tree: Vec<i32>,
    n: i32,
}

impl IndexTree {
    pub fn new(size: i32) -> Self {
        let mut tree: Vec<i32> = vec![];
        for _ in 0..size + 1 {
            tree.push(0);
        }
        Self { tree, n: size }
    }

    pub fn value(&mut self, index: i32) -> i32 {
        if index == 0 {
            return self.sum(0);
        } else {
            return self.sum(index) - self.sum(index - 1);
        }
    }

    pub fn sum(&mut self, i: i32) -> i32 {
        let mut index = i + 1;
        let mut ret = 0;
        while index > 0 {
            ret += self.tree[index as usize];
            index -= index & -index;
        }
        return ret;
    }

    pub fn add(&mut self, i: i32, d: i32) {
        let mut index = i + 1;
        while index <= self.n {
            self.tree[index as usize] += d;
            index += index & -index;
        }
    }
}

// 感谢黄汀同学
// 弄出了时间复杂度O(N)的过程
// 和大厂刷题班，第10节，jump game类似
fn min_jump2(jump: &mut Vec<i32>) -> i32 {
    let nn = jump.len() as i32;
    let mut ans = nn;
    let mut next = jump[0];
    if next >= nn {
        return 1;
    }
    if next + jump[next as usize] >= nn {
        return 2;
    }
    // dp[i] : 来到i位置，最少跳几步？
    let mut dp: Vec<i32> = vec![];
    for _ in 0..nn + 1 {
        dp.push(nn);
    }
    // dis[i] : <= i步的情况下，最远能跳到哪？
    let mut dis: Vec<i32> = vec![];
    for _ in 0..nn {
        dis.push(0);
    }
    // 如果从0开始向前跳，<=1步的情况下，最远当然能到next
    dis[1] = next;
    // 如果从0开始向前跳，<=2步的情况下，最远可能比next + jump[next]要远，
    // 这里先设置，以后可能更新
    dis[2] = next + jump[next as usize];
    dp[(next + jump[next as usize]) as usize] = 2;
    let mut step = 1;
    for i in 1..nn {
        if i > dis[step as usize] {
            step += 1;
        }
        dp[i as usize] = get_min(dp[i as usize], step + 1);
        next = i + jump[i as usize];
        if next >= nn {
            ans = get_min(ans, dp[i as usize] + 1);
        } else if dp[next as usize] > dp[i as usize] + 1 {
            dp[next as usize] = dp[i as usize] + 1;
            dis[dp[next as usize] as usize] = get_max(dis[dp[next as usize] as usize], next);
        }
    }
    return ans;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}