2023-06-20：给定一个长度为N的数组arr，arr[i]表示宝石的价值 你在某天遇到X价值的宝石， X价值如果是所有剩余宝石价值中的最小值，你会将该宝石送人 X价值如果不是所有剩余宝石价值中的

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

// 暴力方法
// 为了验证
func days1(diamonds []int) int {
	arr := make([]int, len(diamonds))
	copy(arr, diamonds)
	ans := 0
	for len(arr) > 0 {
		ans++
		deal(&arr)
	}
	return ans
}

// 暴力方法
// 为了验证
func deal(arr *[]int) {
	head := (*arr)[0]
	*arr = (*arr)[1:]
	min := head
	for _, num := range *arr {
		min = int(math.Min(float64(min), float64(num)))
	}
	if head > min {
		*arr = append(*arr, head)
	}
}

// 正式方法
// 时间复杂度O(N * (logN)的平方)
func days2(diamonds []int) int {
	// n : 位置
	n := len(diamonds)
	// 1 ~ n : 1
	it := NewIndexTree(n)
	//  7 6 2...
	//  1 2 3....
	st := NewSegmentTree(diamonds)
	days := 0
	find, start := 1, 1
	for it.SumRange(1, n) != 0 {
		// start ..... find(后续....最小值，最左的位置)
		find = findMin(st, start, n)
		days += daysCount(it, start, find, n)
		//  1
		// find
		it.Add(find, -1)
		st.Update(find, math.MaxInt32)
		start = find
	}
	return days
}

func findMin(st *SegmentTree, start, n int) int {
	// start....n 左部分  1 ~ start-1 右
	var l, r, min = n, 1, st.Min(1, n)
	if st.Min(start, n) == min {
		l = start
		r = n
	} else {
		l = 1
		r = start - 1
	}
	var m, ans = -1, -1
	for l  0 {
		ret += it.tree[i]
		i -= i & -i
	}
	return ret
}

func (it *IndexTree) SumRange(l, r int) int {
	return it.Sum(r) - it.Sum(l-1)
}

func (it *IndexTree) Add(i, d int) {
	for i > 1
	if L  mid {
		st.update(L, R, C, mid+1, r, rt> 1
	ans := math.MaxInt32
	if L  mid {
		ans = int(math.Min(float64(ans), float64(st.minQuery(L, R, mid+1, r, rt

use std::cmp;
use std::time::SystemTime;

struct IndexTree {
    tree: Vec,
    n: i64,
}

impl IndexTree {
    fn new(size: i64) -> IndexTree {
        let tree = vec![0; (size + 1) as usize];
        let mut it = IndexTree {
            tree: tree,
            n: size,
        };
        for i in 1..=size {
            it.add(i, 1);
        }
        it
    }

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

    fn sum_range(&self, l: i64, r: i64) -> i64 {
        self.sum(r) - self.sum(l - 1)
    }

    fn add(&mut self, mut i: i64, d: i64) {
        while i ,
}

impl SegmentTree {
    fn new(arr: &[i64]) -> SegmentTree {
        let n = arr.len() as i64;
        let min = vec![0; ((n + 1) > 1;
        if L  mid {
            self.update_segment(L, R, C, mid + 1, r, rt  i64 {
        if L > 1;
        let mut ans = i64::MAX;
        if L  mid {
            ans = cmp::min(ans, self.min_query(L, R, mid + 1, r, rt  i64 {
        self.min_query(l, r, 1, self.n, 1)
    }
}

fn days1(diamonds: &mut [i64]) -> i64 {
    let mut arr = diamonds.to_vec();
    let mut ans = 0;
    while !arr.is_empty() {
        ans += 1;
        deal(&mut arr);
    }
    ans
}

fn deal(arr: &mut Vec) {
    let head = arr.remove(0);
    let mut min0 = head;
    for a in arr.iter() {
        min0 = min0.min(*a);
    }
    if head > min0 {
        arr.push(head);
    }
}

fn days2(diamonds: &[i64]) -> i64 {
    let n = diamonds.len() as i64;
    let mut it = IndexTree::new(n);
    let mut st = SegmentTree::new(diamonds);
    let mut days = 0;
    let mut find = 1;
    let mut start = 1;
    while it.sum_range(1, n) != 0 {
        find = find_min(&st, start, n);
        days += days_count(&it, start, find, n);
        it.add(find, -1);
        st.update(find, i64::MAX);
        start = find;
    }
    days
}

fn find_min(st: &SegmentTree, start: i64, n: i64) -> i64 {
    let (mut l, mut r, mut min) = (n, 1, st.min(1, n));
    if st.min(start, n) == min {
        l = start;
        r = n;
    } else {
        l = 1;
        r = start - 1;
    }
    let (mut m, mut ans) = (-1, -1);
    while l > 1;
        if st.min(l, m) == min {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    ans
}

fn days_count(it: &IndexTree, start: i64, find: i64, n: i64) -> i64 {
    if start  Vec {
    let mut arr = vec![0; n as usize];
    for i in 0..n {
        arr[i as usize] = ((rand::random::() % v) + v) % v;
    }
    arr
}

fn main() {
    let now = SystemTime::now();

    println!("例子测试开始");
    let arr = vec![3, 1, 4, 3, 1, 2];
    println!("{}", days1(&mut arr.to_vec()));
    println!("{}", days2(&arr));
    println!("例子测试结束");

    let n = 100;
    let v = 100000;
    let test_times = 1000;
    println!("随机测试开始");
    for _ in 0..test_times {
        let n = ((rand::random::() % n) + n) % n + 1;
        let diamonds = random_array(n, v);
        let ans1 = days1(&mut diamonds.clone());
        let ans2 = days2(&diamonds);
        if ans1 != ans2 {
            println!("出错了!");
        }
    }
    println!("随机测试结束");

    println!("性能测试开始");
    let n = 100000;
    let v = 1000000000;
    let diamonds = random_array(n, v);
    println!("宝石数量 : {}", n);
    println!("价值范围 :  {}", v);
    let start = SystemTime::now();
    days2(&diamonds);
    let end = SystemTime::now();
    println!(
        "运行时间 : {} 毫秒",
        end.duration_since(start).unwrap().as_millis()
    );

    println!("性能测试结束");
}