Rust: Segment Tree Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst, we map all n distinct sorted values of nums into their ordering index (0-based).
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst, we map all n distinct sorted values of nums into their ordering index (0-based). \nWe then use a segment tree to maintain two list of indexes, with the first being the indexes of those numbers in nums that are bigger and the second list contains similar indexes that have not been propogated yet.     \n# Approach\n<!-- Describe your approach to solving the problem. -->\nSegment Tree\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N LogN)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n# Code\n```\nuse std::collections::BinaryHeap;\nuse std::collections::BTreeSet;\nuse std::collections::HashMap;\n\nstruct Tree {\n    tree: Vec<((usize, usize), (usize, usize))>,\n    sz: usize\n}\n\nimpl Tree {\n    fn new(m: usize, n: usize) -> Self {\n        Self { tree: vec![((m, m), (m, m)); 4 * n], sz: m }\n    }\n\n    fn add(&mut self, u: usize, left: usize, right: usize, i: usize, val: usize) {\n        if i < left { return } \n        if i >= right {\n            let mut pq = BinaryHeap::from([val, self.tree[u].1.0, self.tree[u].1.1]);\n            if pq.len() > 2 { pq.pop(); } \n            if pq.len() == 2 { self.tree[u].1.1 = pq.pop().unwrap(); }\n            self.tree[u].1.0 = pq.pop().unwrap();\n            return;\n        }\n        if left == right { return }\n\n        let mid = left + (right - left) / 2;\n        self.add(2 * u, left, mid, i, val);\n        self.add(2 * u + 1, mid + 1, right, i, val);\n    }\n\n    fn query(&mut self, u: usize, left: usize, right: usize, i: usize) ->usize {\n        if self.tree[u].1.0 < self.sz {\n            let mut pq = BinaryHeap::from([self.tree[u].0.0, self.tree[u].0.1, \n                                           self.tree[u].1.0, self.tree[u].1.1]);\n            while pq.len() > 2 { pq.pop(); }\n            self.tree[u].0.1 = pq.pop().unwrap();\n            self.tree[u].0.0 = pq.pop().unwrap();\n        \n            if left < right {\n                let mut pq = BinaryHeap::from([self.tree[u].1.0, self.tree[u].1.1, \n                                               self.tree[2 * u].1.0, self.tree[2 * u].1.1]);\n                while pq.len() > 2 { pq.pop(); }\n                self.tree[2 * u].1.1 = pq.pop().unwrap();\n                self.tree[2 * u].1.0 = pq.pop().unwrap();\n\n                let mut pq = BinaryHeap::from([self.tree[u].1.0, self.tree[u].1.1, \n                                               self.tree[2 * u + 1].1.0, self.tree[2 * u + 1].1.1]);\n                while pq.len() > 2 { pq.pop(); }\n                self.tree[2 * u + 1].1.1 = pq.pop().unwrap();\n                self.tree[2 * u + 1].1.0 = pq.pop().unwrap();\n            }\n\n            self.tree[u].1.0 = self.sz;\n            self.tree[u].1.1 = self.sz;\n        }\n\n        if left == right { return self.tree[u].0.1 }\n\n        let mid = left + (right - left) / 2;\n\n        if i <= mid { return self.query(2 * u, left, mid, i) }\n        self.query(2 * u + 1, mid + 1, right, i)\n    }\n}\n\nimpl Solution {\n    pub fn second_greater_element(nums: Vec<i32>) -> Vec<i32> {\n        let mut temp = BTreeSet::new();\n        for a in &nums { temp.insert(*a); }\n\n        let mut mp = HashMap::<i32, usize>::new();\n        for a in temp.iter() {\n            let sz = mp.len();\n            mp.insert(*a, sz);\n        }\n\n        let n = mp.len() + 1;\n        let m = nums.len();\n        let mut tree = Tree::new(m, n);\n        let mut ret = vec![];\n\n        for i in (0 .. m).rev() {\n            let j = *mp.get(&nums[i]).unwrap();\n            tree.add(1, 0, n - 1, j, i);\n            let k = tree.query(1, 0, n - 1, j + 1);\n            let temp = if k == m { -1 } else { nums[k] };\n            ret.push(temp);\n        }\n        ret.reverse();\n\n        ret\n    } \n}\n```
['Rust']