[C++] Binary Search, O((m + n)log(Max - Min)), Explained
Divide nums1 and nums2 into two parts by sign, with left half <= 0, right half > 0, denoted as l1, r1, l2, r2, so 4 combinations of subarrays of nums1 and nums2
1. Divide nums1 and nums2 into two parts by sign, with left half <= 0, right half > 0, denoted as l1, r1, l2, r2, so 4 combinations of subarrays of nums1 and nums2 in total, i.e. (l1, l2), (l1, r2), (r1, l2), (r1, r2)\n2. Binary search the answer, which is guaranteed to be in the range of [Min, Max], where Min and Max are the minimum and maximum product. So initialize the search range as [left = Min, right = Max], for each mid = (left + right) >> 1, count how many products <= mid in the 4 combinations / matrices above. And reverse the subarrays to make the matrices sorted when necessary. \n3. If the number of products <= mid is exactly k, return the Max product <= mid.\n\nNote: \n1. For subarrays a[0, 1, ..., n - 1] and b[0, 1 ..., m - 1], their products can be represented as a matrix c[x][y] = a[x] * b[y] (We don\'t really represent it because that would be O(nm) complexity). And for the matrix to be sorted: we actually mean every row and column are sorted ascendingly.\n2. To find how many elements in a sorted matrix <= mid, please refer https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/\n\n\n\n```\n#define ll long long\n\nclass Solution {\npublic:\n    // refer: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/\n    inline ll countInMatrix(vector<ll>& a, vector<ll>& b, ll mid, ll& Max) {\n        ll n = a.size(), m = b.size();\n        // matrix c[x][y] := a[x] * b[y]\n        ll x = n - 1, y = 0;\n        ll cnt = 0;\n        \n        while (x >= 0 && y < m) {\n            if (a[x] * b[y] <= mid) {\n                Max = max(Max, a[x] * b[y]);\n                cnt += x + 1;\n                y++;\n            }\n            else {\n                x--;\n            }\n        }\n        \n        return cnt;\n    }\n     \n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        // divide into four combinations by positive / negative, represented in 4 sorted matrices\n        // binary search by value\n        // suppose mid = (left + right) >> 1; count how many elements <= mid in those 4 matrices\n        \n        ll n1 = nums1.size(), n2 = nums2.size();\n        ll p1, p2;\n        for (ll i = 0; i <= n1; ++i) {\n            if (i == n1 || nums1[i] > 0) {\n                p1 = i;\n                break;\n            }\n        }\n        for (ll i = 0; i <= n2; ++i) {\n            if (i == n2 || nums2[i] > 0) {\n                p2 = i;\n                break;\n            }\n        }\n        \n        vector<ll> l1(nums1.begin(), nums1.begin() + p1);\n        vector<ll> r1(nums1.begin() + p1, nums1.end());\n        vector<ll> l2(nums2.begin(), nums2.begin() + p2);\n        vector<ll> r2(nums2.begin() + p2, nums2.end());\n        \n        vector<ll> l1r(l1); // l1 reverse\n        vector<ll> r1r(r1);\n        vector<ll> l2r(l2);\n        vector<ll> r2r(r2);\n        reverse(l1r.begin(), l1r.end());\n        reverse(r1r.begin(), r1r.end());\n        reverse(l2r.begin(), l2r.end());\n        reverse(r2r.begin(), r2r.end());\n        \n        ll left = LLONG_MAX, right = LLONG_MIN;\n        vector<ll> t1 = {0, p1 - 1, p1, n1 - 1};\n        vector<ll> t2 = {0, p2 - 1, p2, n2 - 1};\n        for (ll i = 0; i < 4; ++i) {\n            if (t1[i] < 0 || t1[i] >= n1) continue;\n            for (ll j = 0; j < 4; ++j) {\n                if (t2[j] < 0 || t2[j] >= n2) continue;\n                left = min(left, (ll)nums1[t1[i]] * nums2[t2[j]]);\n                right = max(right, (ll)nums1[t1[i]] * nums2[t2[j]]);\n            }\n        }\n        \n        while (left <= right) {\n            ll mid = (left + right) >> 1;\n            \n            ll cur = 0;\n            ll Max = LLONG_MIN;\n            cur += countInMatrix(l1, r2r, mid, Max);\n            cur += countInMatrix(l1r, l2r, mid, Max);\n            cur += countInMatrix(r1r, l2, mid, Max);\n            cur += countInMatrix(r1, r2, mid, Max);\n            \n            if (cur == k) return Max;\n            else if (cur > k) right = mid - 1;\n            else left = mid + 1;\n        }\n        \n        return left;\n    }\n};\n```
['C', 'Binary Tree']