给你一个下标从 1 开始、长度为 n 的整数数组 nums 。
现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。
你需要使用 n 次操作，将 nums 的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：
·如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。
·如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。
·如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。
·如果仍然相等，那么将 nums[i] 追加到 arr1 。
连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。
返回整数数组 result 。
示例 1：
输入：nums = [2,1,3,3]
输出：[2,3,1,3]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
在 4 次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，连接形成的数组 result 是 [2,3,1,3] 。
示例 2：
输入：nums = [5,14,3,1,2]
输出：[5,3,1,2,14]
解释：在前两次操作后，arr1 = [5] ，arr2 = [14] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[4] 追加到 arr1 。
在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[5] 追加到 arr1 。
在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
因此，连接形成的数组 result 是 [5,3,1,2,14] 。
示例 3：
输入：nums = [3,3,3,3]
输出：[3,3,3,3]
解释：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
因此，连接形成的数组 result 是 [3,3,3,3] 。
提示：
·3 <= n <= 105
·1 <= nums[i] <= 109
题目大意：按照规则在两个新数组中添加原数组的元素，返回两个新数组拼接后的数组。
分析：
（1）添加元素需依据两个新数组中严格大于当前元素的元素数量，如果采用线性统计的方式，整个算法的时间复杂度达到O(N2)，而数据规模为105，因此在该时间复杂度下会超时。由此可见本题的关键是需要设计时间复杂度更小的数据统计算法；
（2）基于（1），考虑使用树状数组快速查找数组中严格大于val的元素数量，分别对两个新数组arr1和arr2设立对应的树状数组tree1和tree2，用于记录两个数组中出现的元素。遍历到原数组的i号元素时就可以用树状数组分别计算两个新数组中严格大于nums[i]的元素数量；
（3）由于元素放入哪个数组仅与该元素和其它元素的大小关系相关，因此可将数组中的元素按大小关系离散化。
class BinaryIndexedTree{
public:
BinaryIndexedTree(int N):_N(N+1),_tree(N+1){}
void add(int i){
while(i<_N){
++_tree[i];
i+=i&(-i);
}
}
int count(int i){
int ans=0;
while(i>0){
ans+=_tree[i];
i-=i&(-i);
}
return ans;
}
private:
vector<int> _tree;
int _N;
};
class Solution {
public:
vector<int> resultArray(vector<int>& nums) {
int N=nums.size(),sum1,sum2;
vector<int> arr1={nums[0]},arr2={nums[1]},newNums=nums;
unordered_map<int,int> index;
BinaryIndexedTree tree1(N+1),tree2(N+1);
sort(newNums.begin(),newNums.end());
for(int i=0;i<N;++i) index[newNums[i]]=i+1;
tree1.add(index[nums[0]]);
tree2.add(index[nums[1]]);
for(int i=2,sum1,sum2;i<N;++i){
sum1=arr1.size()-tree1.count(index[nums[i]]);
sum2=arr2.size()-tree2.count(index[nums[i]]);
if(sum1>sum2||sum1==sum2&&arr1.size()<=arr2.size()){
arr1.emplace_back(nums[i]);
tree1.add(index[nums[i]]);
}
else{
arr2.emplace_back(nums[i]);
tree2.add(index[nums[i]]);
}
}
arr1.insert(arr1.end(),arr2.begin(),arr2.end());
return arr1;
}
};