给定一个长度为N的数组arr，arr[i]表示宝石的价值

你在某天遇到X价值的宝石，

X价值如果是所有剩余宝石价值中的最小值，你会将该宝石送人

X价值如果不是所有剩余宝石价值中的最小值，你会将该宝石放到所有宝石的最后

返回把宝石都送人需要多少天

比如arr = [3,1,4,3,1,2]

在第1天，你遇到了价值3的宝石，但是3并不是所有剩余宝石的价值最小值

所以你把3放在了所有宝石的最后，arr = [1,4,3,1,2,3]

在第2天，你遇到了价值1的宝石，1是所有剩余宝石的价值最小值

所以你把价值1的宝石送人，arr = [4,3,1,2,3]

在第3天，你把价值4的宝石放到最后，arr = [3,1,2,3,4]

在第4天，你把价值3的宝石放到最后，arr = [1,2,3,4,3]

在第5天，你送出了价值1的宝石，arr = [2,3,4,3]

在第6天，你送出了价值2的宝石，arr = [3,4,3]

在第7天，你送出了价值3的宝石，arr = [4,3]

在第8天，你把价值4的宝石放到最后，arr = [3,4]

在第9天，你送出了价值3的宝石，arr = [4]

在第10天，你送出了价值4的宝石，宝石已经没有了。

所以返回10。

1 <= N <= 10的5次方，

1 <= 宝石价值 <= 10的9次方。

1.第一个方法(days1)使用了暴力的方式，通过遍历数组并移动宝石来模拟每一天的操作，直到所有宝石都被送出。时间复杂度较高。

2.第二个方法(days2)使用了更高效的算法。首先构建了一个支持查询累加和和最小值的数据结构（IndexTree和SegmentTree）。然后利用这些数据结构来计算送出所有宝石需要的天数。具体步骤如下：

2.1.初始化累加和数据结构(it)和最小值数据结构(st)。

2.2.设定起始位置(start)为1，找到剩余宝石中的最小值(find)。

2.3.计算从起始位置到最小值之间的宝石总数(daysCount)。

2.4.将最小值送出，更新累加和数据结构(it)和最小值数据结构(st)。

2.5.更新起始位置(start)为最小值。

2.6.重复上述步骤直到所有宝石都被送出。

2.7.返回送出宝石所需的天数。

时间复杂度和空间复杂度如下：

方法1（days1）：

• 时间复杂度：其中N是宝石数组的长度。构建IndexTree和SegmentTree所需的时间复杂度为O(N * logN)。每次查询最小值的时间复杂度为O(logN)，总共进行N次查询。因此，总的时间复杂度，方法2的时间复杂度。在时间复杂度上，方法2优于方法1。方法1的空间复杂度为O(N)，方法2的空间复杂度为O(N)。在空间复杂度上，两种方法相同。

  go完整代码如下：

  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 <= r {
  		m = (l + r) / 2
  		if st.Min(l, m) == min {
  			ans = m
  			r = m - 1
  		} else {
  			l = m + 1
  		}
  	}
  	return ans
  }
  
  func daysCount(it *IndexTree, start, find, n int) int {
  	if start <= find {
  		return it.SumRange(start, find)
  	} else {
  		return it.SumRange(start, n) + it.SumRange(1, find)
  	}
  }
  
  // 支持查询累加和
  type IndexTree struct {
  	tree []int
  	n    int
  }
  
  func NewIndexTree(size int) *IndexTree {
  	it := &IndexTree{
  		tree: make([]int, size+1),
  		n:    size,
  	}
  	for i := 1; i <= size; i++ {
  		it.Add(i, 1)
  	}
  	return it
  }
  
  func (it *IndexTree) Sum(i int) int {
  	ret := 0
  	for i > 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 <= it.n {
  		it.tree[i] += d
  		i += i & -i
  	}
  }
  
  // 支持查询最小值
  type SegmentTree struct {
  	n   int
  	min []int
  }
  
  func NewSegmentTree(arr []int) *SegmentTree {
  	n := len(arr)
  	st := &SegmentTree{
  		n:   n,
  		min: make([]int, (n+1)<<2),
  	}
  	for i := 1; i <= n; i++ {
  		st.Update(i, arr[i-1])
  	}
  	return st
  }
  
  func (st *SegmentTree) Update(i, v int) {
  	st.update(i, i, v, 1, st.n, 1)
  }
  
  func (st *SegmentTree) update(L, R, C, l, r, rt int) {
  	if L <= l && r <= R {
  		st.min[rt] = C
  		return
  	}
  	mid := (l + r) >> 1
  	if L <= mid {
  		st.update(L, R, C, l, mid, rt<<1)
  	}
  	if R > mid {
  		st.update(L, R, C, mid+1, r, rt<<1|1)
  	}
  	st.pushUp(rt)
  }
  
  func (st *SegmentTree) pushUp(rt int) {
  	st.min[rt] = int(math.Min(float64(st.min[rt<<1]), float64(st.min[rt<<1|1])))
  }
  
  func (st *SegmentTree) Min(l, r int) int {
  	return st.minQuery(l, r, 1, st.n, 1)
  }
  
  func (st *SegmentTree) minQuery(L, R, l, r, rt int) int {
  	if L <= l && r <= R {
  		return st.min[rt]
  	}
  	mid := (l + r) >> 1
  	ans := math.MaxInt32
  	if L <= mid {
  		ans = int(math.Min(float64(ans), float64(st.minQuery(L, R, l, mid, rt<<1))))
  	}
  	if R > mid {
  		ans = int(math.Min(float64(ans), float64(st.minQuery(L, R, mid+1, r, rt<<1|1))))
  	}
  	return ans
  }
  
  // 为了测试
  func randomArray(n, v int) []int {
  	arr := make([]int, n)
  	for i := 0; i < n; i++ {
  		arr[i] = rand.Intn(v)
  	}
  	return arr
  }
  
  // 为了测试
  func main() {
  	rand.Seed(time.Now().UnixMilli())
  	fmt.Println("例子测试开始")
  	arr := []int{3, 1, 4, 3, 1, 2}
  	fmt.Println(days1(arr))
  	fmt.Println(days2(arr))
  	fmt.Println("例子测试结束")
  
  	N := 100
  	V := 100000
  	testTimes := 1000
  	fmt.Println("随机测试开始")
  	for i := 0; i < testTimes; i++ {
  		n := rand.Intn(N) + 1
  		diamonds := randomArray(n, V)
  		ans1 := days1(diamonds)
  		ans2 := days2(diamonds)
  		if ans1 != ans2 {
  			fmt.Println("出错了!")
  		}
  	}
  	fmt.Println("随机测试结束")
  
  	fmt.Println("性能测试开始")
  	n := 100000
  	v := 1000000000
  	diamonds := randomArray(n, V)
  	fmt.Println("宝石数量 : ", n)
  	fmt.Println("价值范围 : ", v)
  	start := time.Now()
  	days2(diamonds)
  	end := time.Now()
  	fmt.Println("运行时间 : ", end.Sub(start).Milliseconds(), " 毫秒")
  	fmt.Println("性能测试结束")
  }

  

  rust完整代码如下：

  use std::cmp;
  use std::time::SystemTime;
  
  struct IndexTree {
      tree: Vec<i64>,
      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 <= self.n {
              self.tree[i as usize] += d;
              i += i & -i;
          }
      }
  }
  
  struct SegmentTree {
      n: i64,
      min: Vec<i64>,
  }
  
  impl SegmentTree {
      fn new(arr: &[i64]) -> SegmentTree {
          let n = arr.len() as i64;
          let min = vec![0; ((n + 1) << 2) as usize];
          let mut st = SegmentTree { n: n, min: min };
          for i in 1..=n {
              st.update(i, arr[(i - 1) as usize]);
          }
          st
      }
  
      fn update(&mut self, i: i64, v: i64) {
          self.update_segment(i, i, v, 1, self.n, 1);
      }
  
      fn update_segment(&mut self, L: i64, R: i64, C: i64, l: i64, r: i64, rt: i64) {
          if L <= l && r <= R {
              self.min[rt as usize] = C;
              return;
          }
          let mid = (l + r) >> 1;
          if L <= mid {
              self.update_segment(L, R, C, l, mid, rt << 1);
          }
          if R > mid {
              self.update_segment(L, R, C, mid + 1, r, rt << 1 | 1);
          }
          self.push_up(rt);
      }
  
      fn push_up(&mut self, rt: i64) {
          self.min[rt as usize] = cmp::min(
              self.min[(rt << 1) as usize],
              self.min[(rt << 1 | 1) as usize],
          );
      }
  
      fn min_query(&self, L: i64, R: i64, l: i64, r: i64, rt: i64) -> i64 {
          if L <= l && r <= R {
              return self.min[rt as usize];
          }
          let mid = (l + r) >> 1;
          let mut ans = i64::MAX;
          if L <= mid {
              ans = cmp::min(ans, self.min_query(L, R, l, mid, rt << 1));
          }
          if R > mid {
              ans = cmp::min(ans, self.min_query(L, R, mid + 1, r, rt << 1 | 1));
          }
          ans
      }
  
      fn min(&self, l: i64, r: i64) -> 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<i64>) {
      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 <= r {
          m = (l + r) >> 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 <= find {
          it.sum_range(start, find)
      } else {
          it.sum_range(start, n) + it.sum_range(1, find)
      }
  }
  
  fn random_array(n: i64, v: i64) -> Vec<i64> {
      let mut arr = vec![0; n as usize];
      for i in 0..n {
          arr[i as usize] = ((rand::random::<i64>() % 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::<i64>() % 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!("性能测试结束");
  }