2022-08-22：给定一个数组arr，长度为n，最多可以删除一个连续子数组， 求剩下的数组，严格连续递增的子数组最大长度。 n ＜= 10^6。 来自字节。

use rand::Rng;
fn main() {
    let n: i32 = 100;
    let v: i32 = 20;
    let test_time: i32 = 50000;
    println!("测试开始");
    for _ in 0..test_time {
        let mut m = rand::thread_rng().gen_range(0, n);
        if m == 0 {
            m = 1;
        }
        let mut arr = random_array(m, v);
        let ans1 = max_len1(&mut arr);
        let ans2 = max_len2(&mut arr);
        if ans1 != ans2 {
            println!("出错了!");
            break;
        }
    }
    println!("测试结束");
}

// 暴力方法
// 为了验证
fn max_len1(arr: &mut Vec<i32>) -> i32 {
    let mut ans = max(arr);
    let mut n = arr.len() as i32;
    for L in 0..n {
        for R in L..n {
            let mut cur = delete(arr, L, R);
            ans = get_max(ans, max(&mut cur));
        }
    }
    return ans;
}

fn delete(arr: &mut Vec<i32>, L: i32, R: i32) -> Vec<i32> {
    let mut n = arr.len() as i32;
    let mut ans: Vec<i32> = vec![];
    for _ in 0..n - (R - L + 1) {
        ans.push(0);
    }
    let mut index = 0;
    for i in 0..L {
        ans[index as usize] = arr[i as usize];
        index += 1;
    }
    for i in R + 1..n {
        ans[index as usize] = arr[i as usize];
        index += 1;
    }
    return ans;
}

fn max(arr: &mut Vec<i32>) -> i32 {
    if arr.len() == 0 {
        return 0;
    }
    let mut ans = 1;
    let mut cur = 1;
    for i in 1..arr.len() as i32 {
        if arr[i as usize] > arr[(i - 1) as usize] {
            cur += 1;
        } else {
            cur = 1;
        }
        ans = get_max(ans, cur);
    }
    return ans;
}

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

// 正式方法
// 时间复杂度O(N*logN)
fn max_len2(arr: &mut Vec<i32>) -> i32 {
    if arr.len() == 0 {
        return 0;
    }
    let mut n = arr.len() as i32;
    let mut sorted: Vec<i32> = vec![];
    for _ in 0..n {
        sorted.push(0);
    }
    for i in 0..n {
        sorted[i as usize] = arr[i as usize];
    }
    sorted.sort();
    let mut st: SegmentTree = SegmentTree::new(n);
    st.update1(rank(&mut sorted, arr[0]), 1);
    let mut dp: Vec<i32> = vec![];
    for _ in 0..n {
        dp.push(0);
    }
    dp[0] = 1;
    let mut ans = 1;
    // 一个数字也不删！长度！
    let mut cur = 1;
    for i in 1..n {
        let mut rank0 = rank(&mut sorted, arr[i as usize]);
        // (dp[i - 1] + 1)
        let mut p1 = if arr[(i - 1) as usize] < arr[i as usize] {
            dp[(i - 1) as usize] + 1
        } else {
            1
        };
        //			// rank : 就是当前的数字
        //			// 1~rank-1 : 第二个信息的max
        let mut p2 = if rank0 > 1 { st.max1(rank0 - 1) + 1 } else { 1 };
        dp[i as usize] = get_max(p1, p2);
        ans = get_max(ans, dp[i as usize]);
        if arr[i as usize] > arr[(i - 1) as usize] {
            cur += 1;
        } else {
            cur = 1;
        }
        // 我的当前值是rank
        // 之前有没有还是rank的记录！
        if st.get(rank0) < cur {
            st.update1(rank0, cur);
        }
    }
    return ans;
}

fn rank(sorted: &mut Vec<i32>, num: i32) -> i32 {
    let mut l = 0;
    let mut r = sorted.len() as i32 - 1;
    let mut m = 0;
    let mut ans = -1;
    while l <= r {
        m = (l + r) / 2;
        if sorted[m as usize] >= num {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return ans + 1;
}

pub struct SegmentTree {
    pub n: i32,
    pub max: Vec<i32>,
    pub update: Vec<i32>,
}

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

    pub fn get(&mut self, index: i32) -> i32 {
        return self.max0(index, index, 1, self.n, 1);
    }

    pub fn update1(&mut self, index: i32, c: i32) {
        self.update0(index, index, c, 1, self.n, 1);
    }

    pub fn max1(&mut self, right: i32) -> i32 {
        return self.max0(1, right, 1, self.n, 1);
    }

    fn push_up(&mut self, rt: i32) {
        self.max[rt as usize] = get_max(
            self.max[(rt << 1) as usize],
            self.max[(rt << 1 | 1) as usize],
        );
    }

    fn push_down(&mut self, rt: i32, _ln: i32, _rn: i32) {
        if self.update[rt as usize] != -1 {
            self.update[(rt << 1) as usize] = self.update[rt as usize];
            self.max[(rt << 1) as usize] = self.update[rt as usize];
            self.update[(rt << 1 | 1) as usize] = self.update[rt as usize];
            self.max[(rt << 1 | 1) as usize] = self.update[rt as usize];
            self.update[rt as usize] = -1;
        }
    }

    fn update0(&mut self, ll: i32, rr: i32, cc: i32, l: i32, r: i32, rt: i32) {
        if ll <= l && r <= rr {
            self.max[rt as usize] = cc;
            self.update[rt as usize] = cc;
            return;
        }
        let mid = (l + r) >> 1;
        self.push_down(rt, mid - l + 1, r - mid);
        if ll <= mid {
            self.update0(ll, rr, cc, l, mid, rt << 1);
        }
        if rr > mid {
            self.update0(ll, rr, cc, mid + 1, r, rt << 1 | 1);
        }
        self.push_up(rt);
    }

    fn max0(&mut self, ll: i32, rr: i32, l: i32, r: i32, rt: i32) -> i32 {
        if ll <= l && r <= rr {
            return self.max[rt as usize];
        }
        let mid = (l + r) >> 1;
        self.push_down(rt, mid - l + 1, r - mid);
        let mut ans = 0;
        if ll <= mid {
            ans = get_max(ans, self.max0(ll, rr, l, mid, rt << 1));
        }
        if rr > mid {
            ans = get_max(ans, self.max0(ll, rr, mid + 1, r, rt << 1 | 1));
        }
        return ans;
    }
}

// 为了测试
fn random_array(len: i32, v: i32) -> Vec<i32> {
    let mut ans: Vec<i32> = vec![];
    for _ in 0..len {
        ans.push(rand::thread_rng().gen_range(0, v) - rand::thread_rng().gen_range(0, v));
    }
    return ans;
}