将数组清空

难度困难

给你一个包含若干 互不相同 整数的数组 nums ，你需要执行以下操作 直到 **** 数组为空 ：

请你返回需要多少个操作使 nums 为空。

示例 1：

输入：nums = [3,4,-1]

输出：5

Operation Array

1 [4, -1, 3]

2 [-1, 3, 4]

3 [3, 4]

4 [4]

5 []

示例 2：

输入：nums = [1,2,4,3]

输出：5

Operation Array

1 [2, 4, 3]

2 [4, 3]

3 [3, 4]

4 [4]

5 []

示例 3：

输入：nums = [1,2,3]

输出：3

Operation Array

1 [2, 3]

2 [3]

3 []

提示：

# 树状数组 + 排序

树状数组: query(i + 1, j + 1) , 区间 [i, j] 被删除元素的个数: cnt[i, j]

对元素排序，并保留其下标

当前待删除元素下标 i ，上一个被删除元素 pre 作为当前首元素下标

若 $i < pre$ ，需要将 i 之前的剩余元素移到当前数组末尾，并删除 i

若 $i > pre$ ，只需要将 (pre, i) 的剩余元素移到末尾，因为 pre 之前的元素已经到末尾了

移动次数: $i - pre - 1 - cnt[pre + 1, i - 1]$ $i - p re - 1 - c n t [p re + 1, i - 1]$
- $cnt[pre + 1, i - 1]: [pre + 1, i - 1]$ 中被删除的元素个数

	class Solution {
	public long countOperationsToEmptyArray(int[] nums) {
	int n = nums.length;
	Integer[] idx = new Integer[n];
	for (int i = 0; i < n; i++) {
	idx[i] = i;
	}
	Arrays.sort(idx, (o1, o2) -> {
	return nums[o1] - nums[o2];
	});
	tree = new int[n + 2];
	int k = 0;
	long ans = n;
	int pre = -1;
	for (int j = 0; j < n; j++, k++) {
	// 当前最小元素下标
	int i = idx[j];
	if (i < pre) {
	ans += i + n - pre - 1 - k + query(pre + 1) - query(i);
	} else {
	ans += i - pre - 1 - query(i) + query(pre + 1);
	}
	// 更新
	update(i + 1, 1);
	pre = i;
	}
	return ans;
	}

	int[] tree;

	public int query(int x) {
	int ans = 0;
	while (x > 0) {
	ans += tree[x];
	x -= lowBit(x);
	}
	return ans;
	}

	public void update(int x, int v) {
	int n = tree.length;
	while (x < n) {
	tree[x] += v;
	x += lowBit(x);
	}
	}

	public int lowBit(int x) {
	return x & -x;
	}

	}