lc2659
树状数组统计已删除元素，按数值升序遍历元素位置
分前后段计算每次删除的移动步数并累加，求解清空数组的总操作数。
// 树状数组模板
class BIT {
vector<int> tree;
public:
BIT(int n) : tree(n) {}
// 将下标 i 上的数加一
void inc(int i) {
while (i < tree.size()) {
++tree[i];
i += i & -i;
}
}
// 返回闭区间 [1, i] 的元素和
int sum(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x &= x - 1;
}
return res;
}
// 返回闭区间 [left, right] 的元素和
int query(int left, int right) {
return sum(right) - sum(left - 1);
}
};
class Solution {
public:
long long countOperationsToEmptyArray(vector<int> &nums) {
int n = nums.size(), id[n];
iota(id, id + n, 0);
sort(id, id + n, [&](int i, int j) {
return nums[i] < nums[j];
});
long long ans = n; // 先把 n 计入答案
BIT t(n + 1); // 下标从 1 开始
int pre = 1; // 上一个最小值的位置，初始为 1
for (int k = 0; k < n; ++k) {
int i = id[k] + 1; // 下标从 1 开始
if (i >= pre) // 从 pre 移动到 i，跳过已经删除的数
ans += i - pre - t.query(pre, i);
else // 从 pre 移动到 n，再从 1 移动到 i，跳过已经删除的数
ans += n - pre + i - k + t.query(i, pre - 1);
t.inc(i); // 删除 i
pre = i;
}
return ans;
}
};
