Fruits Into Baskets III
<p>You are given two arrays of integers, <code>fruits</code> and <code>baskets</code>, each of length <code>n</code>, where <code>fruits[i]</code> represents the <strong>quantity</strong> of the <code>i<sup>th</sup></code> type of fruit, and <code>baskets[j]</code> represents the <strong>capacity</strong> of the <code>j<sup>th</sup></code> basket.</p>

<p>From left to right, place the fruits according to these rules:</p>

<ul>
	<li>Each fruit type must be placed in the <strong>leftmost available basket</strong> with a capacity <strong>greater than or equal</strong> to the quantity of that fruit type.</li>
	<li>Each basket can hold <b>only one</b> type of fruit.</li>
	<li>If a fruit type <b>cannot be placed</b> in any basket, it remains <b>unplaced</b>.</li>
</ul>

<p>Return the number of fruit types that remain unplaced after all possible allocations are made.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">fruits = [4,2,5], baskets = [3,5,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li><code>fruits[0] = 4</code> is placed in <code>baskets[1] = 5</code>.</li>
	<li><code>fruits[1] = 2</code> is placed in <code>baskets[0] = 3</code>.</li>
	<li><code>fruits[2] = 5</code> cannot be placed in <code>baskets[2] = 4</code>.</li>
</ul>

<p>Since one fruit type remains unplaced, we return 1.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">fruits = [3,6,1], baskets = [6,4,7]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<ul>
	<li><code>fruits[0] = 3</code> is placed in <code>baskets[0] = 6</code>.</li>
	<li><code>fruits[1] = 6</code> cannot be placed in <code>baskets[1] = 4</code> (insufficient capacity) but can be placed in the next available basket, <code>baskets[2] = 7</code>.</li>
	<li><code>fruits[2] = 1</code> is placed in <code>baskets[1] = 4</code>.</li>
</ul>

<p>Since all fruits are successfully placed, we return 0.</p>
</div>

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

<ul>
	<li><code>n == fruits.length == baskets.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= fruits[i], baskets[i] &lt;= 10<sup>9</sup></code></li>
</ul>
Segment Tree; Array; Binary Search; Ordered Set
struct SegmentTree<'a> {
    nums: &'a [i32],
    tr: Vec<i32>,
}

impl<'a> SegmentTree<'a> {
    fn new(nums: &'a [i32]) -> Self {
        let n = nums.len();
        let mut tree = SegmentTree {
            nums,
            tr: vec![0; n * 4],
        };
        tree.build(1, 1, n);
        tree
    }

    fn build(&mut self, u: usize, l: usize, r: usize) {
        if l == r {
            self.tr[u] = self.nums[l - 1];
            return;
        }
        let mid = (l + r) >> 1;
        self.build(u * 2, l, mid);
        self.build(u * 2 + 1, mid + 1, r);
        self.pushup(u);
    }

    fn modify(&mut self, u: usize, l: usize, r: usize, i: usize, v: i32) {
        if l == r {
            self.tr[u] = v;
            return;
        }
        let mid = (l + r) >> 1;
        if i <= mid {
            self.modify(u * 2, l, mid, i, v);
        } else {
            self.modify(u * 2 + 1, mid + 1, r, i, v);
        }
        self.pushup(u);
    }

    fn query(&self, u: usize, l: usize, r: usize, v: i32) -> i32 {
        if self.tr[u] < v {
            return -1;
        }
        if l == r {
            return l as i32;
        }
        let mid = (l + r) >> 1;
        if self.tr[u * 2] >= v {
            return self.query(u * 2, l, mid, v);
        }
        self.query(u * 2 + 1, mid + 1, r, v)
    }

    fn pushup(&mut self, u: usize) {
        self.tr[u] = self.tr[u * 2].max(self.tr[u * 2 + 1]);
    }
}

impl Solution {
    pub fn num_of_unplaced_fruits(fruits: Vec<i32>, baskets: Vec<i32>) -> i32 {
        let mut tree = SegmentTree::new(&baskets);
        let n = baskets.len();
        let mut ans = 0;
        for &x in fruits.iter() {
            let i = tree.query(1, 1, n, x);
            if i < 0 {
                ans += 1;
            } else {
                tree.modify(1, 1, n, i as usize, 0);
            }
        }
        ans
    }
}
