<p>You are given a string <code>num</code> representing <strong>the digits</strong> of a very large integer and an integer <code>k</code>. You are allowed to swap any two adjacent digits of the integer <strong>at most</strong> <code>k</code> times.</p>

<p>Return <em>the minimum integer you can obtain also as a string</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/17/q4_1.jpg" style="width: 500px; height: 40px;" />
<pre>
<strong>Input:</strong> num = &quot;4321&quot;, k = 4
<strong>Output:</strong> &quot;1342&quot;
<strong>Explanation:</strong> The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;100&quot;, k = 1
<strong>Output:</strong> &quot;010&quot;
<strong>Explanation:</strong> It&#39;s ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;36789&quot;, k = 1000
<strong>Output:</strong> &quot;36789&quot;
<strong>Explanation:</strong> We can keep the number without any swaps.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>num</code> consists of only <strong>digits</strong> and does not contain <strong>leading zeros</strong>.</li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>

class SegmentTreeMax:
    def __init__(self, data):
        self.data = data
        self.tree = [-1] * (4*len(self.data))
        self.tree2 = [-1] * (4*len(self.data))
        self.lazy = [None] * (4*len(self.data))
        self._init(1, 0, len(self.data) - 1) # tree node is 1-indexed, range are 0-indexed

    def _init(self, i, l, r):
        if l == r:
            self.tree[i] = self.data[l]
            self.tree2[i] = l
            return self.tree[i],self.tree2[i]
        m = (l+r)//2
        if self._init(i*2, l, m) < self._init(i*2+1, m+1,r):
            self.tree[i],self.tree2[i] = self._init(i*2, l, m)
        else:
            self.tree[i],self.tree2[i] = self._init(i*2+1, m+1,r)

        return self.tree[i],self.tree2[i]

    def _update(self, i, ql, qr, value, l, r):
        
        if self.lazy[i] != None:
            self.tree[i] = self.lazy[i]
            if l!=r: # not leaf node
                self.lazy[i*2] = self.lazy[i]
                self.lazy[i*2+1] = self.lazy[i]
            self.lazy[i] = None
            
        if qr < l or r < ql:  # [ql, qr] and [l, r] don't intersect
            return
        if ql == l and r == qr:
            self.tree[i] = value
            self.tree2[i] = r
            if l != r: # not leaf node                
                self.lazy[i*2] = value
                self.lazy[i*2+1] = value

            return

        m = (l+r)//2        
        if qr <= m:
            self._update(i*2, ql, qr, value, l, m)
        elif m < ql:
            self._update(i*2+1, ql, qr, value, m+1, r)
        else: # ql <= m < qr
            self._update(i*2, ql, m, value, l, m)
            self._update(i*2+1, m+1, qr, value, m+1, r)

        if self.tree[i*2] < self.tree[i*2+1]:
            self.tree[i] = self.tree[i*2]
            self.tree2[i] = self.tree2[i*2]
        else:
            self.tree[i] = self.tree[i*2+1]
            self.tree2[i] = self.tree2[i*2+1]


    def _query(self, i, ql, qr, l, r):
        if qr < l or r < ql:  # [ql, qr] and [l, r] don't intersect.
            return -1,-1
        
        if self.lazy[i] != None:
            self.tree[i] = self.lazy[i]     # make pending updates to this node
            if l != r: # not a leaf node
                self.lazy[i*2] = self.lazy[i] # since we are not yet updating children, we need to set lazy values for the children 
                self.lazy[i*2+1] = self.lazy[i]
            self.lazy[i] = None # Unset the lazy value for current node as it has been updated 
        

        if ql == l and r == qr:
            return self.tree[i],self.tree2[i]
        m = (l+r)//2        
        if qr <= m:
            return self._query(i*2, ql, qr, l, m)
        elif m < ql:
            return self._query(i*2+1, ql, qr, m+1, r)
        else: # ql <= m < qr
            ltree,ltree2 = self._query(i*2, ql, m, l, m) 
            rtree,rtree2 = self._query(i*2+1, m+1, qr, m+1, r)
            if ltree < rtree:
                return ltree,ltree2
            else:
                return rtree,rtree2


    # range update 
    def update(self, left, right, value):
        self._update(1, left, right, value, 0, len(self.data) - 1)
    
    # range query
    def query(self, left, right):
        return self._query(1, left, right, 0, len(self.data) - 1)
    
    def getMin(self):
        return self.query(0,len(self.data)-1)




def count_greater_left(nums):
    n = len(nums)
    result = [0] * n
    indexed_nums = list(enumerate(nums))
    
    def merge_count(left, right):
        i, j = 0, 0
        temp = []
        while i < len(left) and j < len(right):
            if left[i][1] <= right[j][1]:
                temp.append(left[i])
                i += 1
            else:
                temp.append(right[j])
                # Count how many elements from the left are greater than right[j]
                result[right[j][0]] += len(left) - i
                j += 1
        temp.extend(left[i:])
        temp.extend(right[j:])
        return temp
    
    def iterative_merge_sort(arr):
        width = 1
        while width < len(arr):
            for i in range(0, len(arr), 2 * width):
                left = arr[i:i + width]
                right = arr[i + width:i + 2 * width]
                merged = merge_count(left, right)
                arr[i:i + len(merged)] = merged
            width *= 2

    iterative_merge_sort(indexed_nums)
    
    return result


class Solution:
    def minInteger(self, num: str, k: int) -> str:
        n = len(num)
        
        numx = []
        for i in range(n):
            numx.append(int(num[i]))
        b = count_greater_left(numx)
        #print(f"b={b}")

        num2 = []
        for i in range(n):
            num2.append((int(num[i]),i))
        num2.sort()
        #print(f"num2={num2}")
        left = ""
        i = 0
        h = {}
        while i < n and k > 0:

            while  i < n:
                if i in h:
                    i += 1
                    continue
                v,j = num2[i]
                if b[j] <= k:
                    left += str(v)
                    k -= b[j]
                    h[i] = True
                    i += 1
                    if b[j]==0:
                        i = 0

                    break
                else:
                    
                    #rightList.append((j,v))
                    b[j] -= 1
                    #print(f"  b={b}")
                    i += 1
        '''
        while i < n:
            v,j = num2[i]
            rightList.append((j,v))
            i += 1
        '''
        
        rightList = []
        for i in range(n):
            if i not in h:
                v,j = num2[i]
                rightList.append((j,v))

        #print(rightList)
        rightList.sort()
        right = ""
        for _,v in rightList:
            right += str(v)
        
        return left + right
24800