<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 Solution {
public:

    void build(int nl, int nr, int tidx, vector<int> &nums, vector<pair<int, int>> &tree) {
        if(nl == nr) {
            tree[tidx] = {nums[nl], nl};
            return;
        }
        int mid = (nl+nr)/2;

        build(nl, mid, 2*tidx+1, nums, tree);
        build(mid+1, nr, 2*tidx+2, nums, tree);

        if(tree[2*tidx+1].first < tree[2*tidx+2].first)  {
            tree[tidx] = tree[2*tidx+1];
        } else if(tree[2*tidx+1].first > tree[2*tidx+2].first) {
            tree[tidx] = tree[2*tidx+2];
        } else {
            if(tree[2*tidx+1].second < tree[2*tidx+2].second) {
                tree[tidx] = tree[2*tidx+1];
            } else {
                tree[tidx] = tree[2*tidx+2]; 
            }
        }
    }

    void update(int nl, int nr, int tidx, int idx, vector<pair<int, int>> &tree) {
        if(nl == nr) {
            tree[tidx] = {INT_MAX, INT_MAX};
            return; 
        }

        int mid = (nl+nr)/2;

        if(idx <= mid) {
            update(nl, mid, 2*tidx+1, idx, tree);
        } else {
            update(mid+1, nr, 2*tidx+2, idx, tree); 
        }

        if(tree[2*tidx+1].first < tree[2*tidx+2].first)  {
            tree[tidx] = tree[2*tidx+1];
        } else if(tree[2*tidx+1].first > tree[2*tidx+2].first) {
            tree[tidx] = tree[2*tidx+2];
        } else {
            if(tree[2*tidx+1].second < tree[2*tidx+2].second) {
                tree[tidx] = tree[2*tidx+1];
            } else {
                tree[tidx] = tree[2*tidx+2]; 
            }
        }
    }

    pair<int, int> query(int nl, int nr, int tidx, int l, int r, vector<pair<int, int>> &tree) {
        if(nl > r or nr < l) return {INT_MAX, INT_MAX};
        if(nl >= l and nr <= r) return tree[tidx];

        int mid = (nl+nr)/2;

        pair<int, int> left = query(nl, mid, 2*tidx+1, l, r, tree);
        pair<int, int> right = query(mid+1, nr, 2*tidx+2, l, r, tree);

        if(left.first < right.first)  {
            return left;
        } else if(left.first > right.first) {
            return right; 
        } else {
            if(left.second < right.second) {
                return left;
            } 
        }

        return right;
    }

    void build2(int nl, int nr, int tidx, vector<int> &tree) {
        if(nl == nr) {
            tree[tidx] = 1;
            return; 
        }

        int mid = (nl+nr)/2; 
        build2(nl, mid, 2*tidx+1, tree);
        build2(mid+1, nr, 2*tidx+2, tree);

        tree[tidx] = tree[2*tidx+1] + tree[2*tidx+2];
    }

    void update2(int nl, int nr, int tidx, int idx, vector<int> &tree) {
        if(nl == nr) {
            tree[tidx] = 0; 
            return; 
        }
        int mid = (nl+nr)/2; 

        if(idx <= mid){
            update2(nl, mid, 2*tidx+1, idx, tree);
        } else {
            update2(mid+1, nr, 2*tidx+2, idx, tree);
        }

        tree[tidx] = tree[2*tidx+1] + tree[2*tidx+2];
    }

    int query2(int nl, int nr, int tidx, int l, int r, vector<int> &tree) {
        if(nl > r or nr < l) return 0;
        if(nl >= l and nr <= r) return tree[tidx];

        int mid = (nl+nr)/2;
        int left = query2(nl, mid, 2*tidx+1, l, r, tree);
        int right = query2(mid+1, nr, 2*tidx+2, l, r, tree);

        return left + right;
    }  

    int getIdx(int n, int k, vector<int> &tree, int i) {
        int lo = 0, hi = n-1;
        int idx = -1; 
        while(lo <= hi) {
            int mid = (lo+hi)/2; 
            
            int sum = query2(0, n-1, 0, 0, mid, tree); 
            // if(i == 1) {
            //     cout<<mid<<" "<<sum<<" "<<lo<<" "<<hi<<" "<<k<<endl;
            // }
            
            if(sum-1 > k) {
                hi=mid-1; 
            } else {
                idx=mid;
                lo=mid+1;
            }
        }

        return idx; 
    }

    string minInteger(string num, int k) {
        int n = num.size();

        vector<int> nums(n);
        for(int i = 0; i < n; i++) {
            nums[i] = num[i]-'0'; 
        }

        vector<pair<int, int>> tree1(4*n+1, {0, 0});
        build(0,n-1,0, nums, tree1);
        vector<int> tree2(4*n+1, 1); 
        build2(0, n-1, 0, tree2); 

        string ans = num;

        int i = 0; 
        vector<bool> vis(n,false);
        while(k > 0 and i < n) {
            
            int idx = getIdx(n, k, tree2, i); 
            pair<int, int> mini = query(0, n-1, 0, 0, idx, tree1);

            int valIdx = mini.second;
            int val = mini.first;
            // cout<<valIdx<<endl;
            int temp = query2(0, n-1, 0, valIdx, n-1, tree2); 
            int numberOfZeroes = n-valIdx-temp; 
            
            int realIdx = numberOfZeroes + valIdx;

            int reqOp = abs(i-realIdx); 
            if(k >= reqOp) {
                k -= reqOp;
                ans[i] = num[valIdx];
            } else {
                break;
            }

            update2(0, n-1, 0, valIdx, tree2);
            update(0, n-1, 0, valIdx, tree1);

            vis[valIdx] = true; 
            i++;     
        }

        for(int j = 0; j < n; j++) {
            if(not vis[j]) {
                ans[i++] = num[j];
            }
        }
        return ans; 

    }   
};
18600