1import java.util.Arrays;
2
3// Class representing a Binary Indexed Tree (Fenwick Tree)
4class BinaryIndexedTree {
5    private int size; // the number of elements in the Binary Indexed Tree
6    private int[] tree; // array that represents the Binary Indexed Tree
7
8    // Constructor that initializes the tree with a given size
9    public BinaryIndexedTree(int size) {
10        this.size = size;
11        this.tree = new int[size + 1];
12    }
13
14    // Updates a value at the given index by a certain delta amount
15    public void update(int index, int delta) {
16        // Loop over the tree and apply updates
17        for (; index <= size; index += index & -index) {
18            tree[index] += delta;
19        }
20    }
21
22    // Queries and returns the cumulative frequency up to a given index
23    public int query(int index) {
24        int sum = 0;
25        // Loop over the tree and calculate the sum
26        for (; index > 0; index -= index & -index) {
27            sum += tree[index];
28        }
29        return sum;
30    }
31}
32
33// Solution class that contains the method for creating the result array
34class Solution {
35    // Method to generate the result array based on certain constraints
36    public int[] resultArray(int[] nums) {
37        // Create a sorted copy of the original array
38        int[] sortedNums = nums.clone();
39        Arrays.sort(sortedNums);
40        int n = sortedNums.length;
41      
42        // Set up two Binary Indexed Trees for processing the arrays
43        BinaryIndexedTree tree1 = new BinaryIndexedTree(n + 1);
44        BinaryIndexedTree tree2 = new BinaryIndexedTree(n + 1);
45      
46        // Initial updates for the first two elements of the nums array
47        tree1.update(Arrays.binarySearch(sortedNums, nums[0]) + 1, 1);
48        tree2.update(Arrays.binarySearch(sortedNums, nums[1]) + 1, 1);
49      
50        // Initialize result arrays and their pointers
51        int[] resultArray1 = new int[n];
52        int[] resultArray2 = new int[n];
53      
54        // Set the first elements of the result arrays
55        resultArray1[0] = nums[0];
56        resultArray2[0] = nums[1];
57      
58        // Pointers for the result arrays
59        int index1 = 1; 
60        int index2 = 1;
61      
62        // Process the rest of the elements in the nums array
63        for (int k = 2; k < n; ++k) {
64            int valuePosition = Arrays.binarySearch(sortedNums, nums[k]) + 1;
65            int a = index1 - tree1.query(valuePosition);
66            int b = index2 - tree2.query(valuePosition);
67            // Compare and decide which array to add the current element to
68            if (a > b) {
69                resultArray1[index1++] = nums[k];
70                tree1.update(valuePosition, 1);
71            } else if (a < b) {
72                resultArray2[index2++] = nums[k];
73                tree2.update(valuePosition, 1);
74            } else if (index1 <= index2) {
75                resultArray1[index1++] = nums[k];
76                tree1.update(valuePosition, 1);
77            } else {
78                resultArray2[index2++] = nums[k];
79                tree2.update(valuePosition, 1);
80            }
81        }
82
83        // Merge the two result arrays into resultArray1
84        for (int k = 0; k < index2; ++k) {
85            resultArray1[index1++] = resultArray2[k];
86        }
87      
88        // Return the merged result array
89        return resultArray1;
90    }
91}
92

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5// BinaryIndexedTree (also known as a Fenwick tree) for efficient 
6// update and query of prefix sums.
7class BinaryIndexedTree {
8private:
9    int size;  // Total number of elements in the array
10    vector<int> tree;  // The tree structure stored as a vector
11
12public:
13    // Constructor to initialize the tree with a given size.
14    BinaryIndexedTree(int size)
15        : size(size), tree(size + 1, 0) {}
16
17    // Updates the tree with a given delta at a specific index.
18    void update(int index, int delta) {
19        for (; index <= size; index += index & -index) {
20            tree[index] += delta;
21        }
22    }
23
24    // Queries the prefix sum up to a given index.
25    int query(int index) {
26        int sum = 0;
27        for (; index > 0; index -= index & -index) {
28            sum += tree[index];
29        }
30        return sum;
31    }
32};
33
34// Solution class containing the method to process the input array
35// and produce the result array.
36class Solution {
37public:
38    // Method to create and return the result array.
39    vector<int> resultArray(vector<int>& nums) {
40        // Copy the input array and sort the copy to facilitate binary index calculations.
41        vector<int> sortedNums = nums;
42        sort(sortedNums.begin(), sortedNums.end());
43
44        int n = nums.size();  // Store the size of the input array.
45      
46        // Create two BinaryIndexedTree instances.
47        BinaryIndexedTree tree1(n + 1);
48        BinaryIndexedTree tree2(n + 1);
49
50        // Update the trees with the first two elements in nums.
51        tree1.update(distance(sortedNums.begin(), lower_bound(sortedNums.begin(), sortedNums.end(), nums[0])) + 1, 1);
52        tree2.update(distance(sortedNums.begin(), lower_bound(sortedNums.begin(), sortedNums.end(), nums[1])) + 1, 1);
53
54        // Initialize two arrays to store elements as we process them.
55        vector<int> arr1 = {nums[0]};
56        vector<int> arr2 = {nums[1]};
57
58        // Process the remaining elements in nums.
59        for (int k = 2; k < n; ++k) {
60            int x = distance(sortedNums.begin(), lower_bound(sortedNums.begin(), sortedNums.end(), nums[k])) + 1;
61            int a = arr1.size() - tree1.query(x);
62            int b = arr2.size() - tree2.query(x);
63            if (a > b) {
64                arr1.push_back(nums[k]);
65                tree1.update(x, 1);
66            } else if (a < b) {
67                arr2.push_back(nums[k]);
68                tree2.update(x, 1);
69            } else if (arr1.size() <= arr2.size()) {
70                arr1.push_back(nums[k]);
71                tree1.update(x, 1);
72            } else {
73                arr2.push_back(nums[k]);
74                tree2.update(x, 1);
75            }
76        }
77
78        // Combine arr1 and arr2 into arr1 as the final result.
79        arr1.insert(arr1.end(), arr2.begin(), arr2.end());
80        return arr1;
81    }
82};
83

1const n: number = 0; // Size of the Binary Indexed Tree
2const bitValues: number[] = []; // Array that represents the tree
3
4// Initializes the Binary Indexed Tree with a specified size
5function initializeBIT(size: number): void {
6    this.n = size;
7    this.bitValues = Array(size + 1).fill(0);
8}
9
10// Updates the Binary Indexed Tree at a specific index by a delta value
11function updateBIT(index: number, delta: number): void {
12    while (index <= n) {
13        bitValues[index] += delta;
14        index += (index & -index);
15    }
16}
17
18// Queries the sum of the range from 1 to a specific index in the Binary Indexed Tree
19function queryBIT(index: number): number {
20    let sum = 0;
21    while (index > 0) {
22        sum += bitValues[index];
23        index -= (index & -index);
24    }
25    return sum;
26}
27
28// Given an array of numbers, returns the resulting array after operations are performed
29function getResultArray(nums: number[]): number[] {
30    const numSorted: number[] = nums.slice().sort((a, b) => a - b);
31    const search = (value: number): number => {
32        let left = 0, right = numSorted.length;
33        while (left < right) {
34            const mid = (left + right) >> 1;
35            if (numSorted[mid] >= value) {
36                right = mid;
37            } else {
38                left = mid + 1;
39            }
40        }
41        return left;
42    };
43    initializeBIT(numSorted.length + 1);
44    const bit1: number[] = Array.from(bitValues);
45    const bit2: number[] = Array.from(bitValues);
46    updateBIT(search(nums[0]) + 1, 1);
47    updateBIT(search(nums[1]) + 1, 1);
48    const arr1: number[] = [nums[0]];
49    const arr2: number[] = [nums[1]];
50    nums.slice(2).forEach(x => {
51        const index: number = search(x) + 1;
52        const countA: number = arr1.length - queryBIT(index); // using global queryBIT
53        const countB: number = arr2.length - queryBIT(index); // using global queryBIT
54        if (countA > countB || (countA === countB && arr1.length <= arr2.length)) {
55            arr1.push(x);
56            updateBIT(index, 1); // using global updateBIT
57        } else {
58            arr2.push(x);
59            updateBIT(index, 1); // using global updateBIT
60        }
61    });
62    return arr1.concat(arr2);
63}
64
65// Note that the code uses this.n and this.bitValues assuming they are members of a BIT class,
66// but the problem statement asks to omit the class, hence global variables n and bitValues are
67// introduced and would need to be passed appropriately if this code is part of a larger system.
68