Since all numbers are distinct, the smallest element can be found and removed efficiently. To count the number of rotations (moves to the end) needed before each removal, we can use a Binary Indexed Tree (Fenwick Tree) to track which elements remain. We process the elements in increasing order, and for each, count how many elements are before it (i.e., how many rotations are needed).
classBIT {
vector<int> tree;
public: BIT(int n) : tree(n+2) {}
voidadd(int i, int v) { for (++i; i < tree.size(); i += i &-i) tree[i] += v; }
intsum(int i) { int s =0; for (++i; i >0; i -= i &-i) s += tree[i]; return s; }
};
classSolution {
public:longlong countOperationsToEmptyArray(vector<int>& nums) {
int n = nums.size();
vector<pair<int,int>> arr;
for (int i =0; i < n; ++i) arr.push_back({nums[i], i});
sort(arr.begin(), arr.end());
BIT bit(n);
for (int i =0; i < n; ++i) bit.add(i, 1);
longlong ans =0;
for (auto& [val, idx] : arr) {
ans += bit.sum(idx-1) +1;
bit.add(idx, -1);
}
return ans;
}
};
import java.util.*;
classBIT {
int[] tree;
BIT(int n) { tree =newint[n+2]; }
voidadd(int i, int v) { for (++i; i < tree.length; i += i &-i) tree[i]+= v; }
intsum(int i) { int s = 0; for (++i; i > 0; i -= i &-i) s += tree[i]; return s; }
}
classSolution {
publiclongcountOperationsToEmptyArray(int[] nums) {
int n = nums.length;
int[][] arr =newint[n][2];
for (int i = 0; i < n; ++i) arr[i]=newint[]{nums[i], i};
Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));
BIT bit =new BIT(n);
for (int i = 0; i < n; ++i) bit.add(i, 1);
long ans = 0;
for (int[] p : arr) {
int idx = p[1];
ans += bit.sum(idx-1) + 1;
bit.add(idx, -1);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classBIT(n: Int) {
val tree = IntArray(n+2)
funadd(i: Int, v: Int) { var i = i+1; while (i < tree.size) { tree[i] += v; i += i and -i } }
funsum(i: Int): Int { var s = 0; var i = i+1; while (i > 0) { s += tree[i]; i -= i and -i }; return s }
}
classSolution {
funcountOperationsToEmptyArray(nums: IntArray): Long {
val n = nums.size
val arr = nums.mapIndexed { i, v -> v to i }.sortedBy { it.first }
val bit = BIT(n)
for (i in0 until n) bit.add(i, 1)
var ans = 0Lfor ((_, idx) in arr) {
ans += bit.sum(idx-1) + 1 bit.add(idx, -1)
}
return ans
}
}
classBIT:
def__init__(self, n: int):
self.tree = [0] * (n+2)
defadd(self, i: int, v: int):
i +=1while i < len(self.tree):
self.tree[i] += v
i += i &-i
defsum(self, i: int) -> int:
i +=1 s =0while i >0:
s += self.tree[i]
i -= i &-i
return s
classSolution:
defcountOperationsToEmptyArray(self, nums: list[int]) -> int:
n = len(nums)
arr = sorted((v, i) for i, v in enumerate(nums))
bit = BIT(n)
for i in range(n):
bit.add(i, 1)
ans =0for _, idx in arr:
ans += bit.sum(idx-1) +1 bit.add(idx, -1)
return ans