Waaaaaggggghhhhhhh
Intuition\n Describe your first thoughts on how to solve this problem. \nLet we have some pairs of collections of numbers (A_i, B_i), for any i any number from 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet we have some pairs of collections of numbers (A_i, B_i), for any i any number from A_i  less or equals to any number from B_i\nLet sum of sizes of A_i is T, and we need find the Kth number of union (A_i) and (B_i) (K starts from 1)\n\nSo:\nif T >= K, we can drop B_i with the maximal floor\nif T < K, we can drop A_i with the minimal ceil and decrease K to the size of this A_i\n\nSo, simultion of this process with drop and resplit pair of the dropped se  \n\n\n# Complexity\n n = max(nums1.length, nums2.length)\n m = min(nums1.length, nums2.length)\n- - Time complexity:\n- O(m*log(m)*log(n))\n \n- Space complexity:\nO(n + m)\n\n# Code\n```\nclass Solution {\n    long lowerCount;\n    long wantedPos;\n\n    public class SmallSplittedLongs {\n        long[] smalls;\n        long[] bigs;\n        int bigCount;\n        int smallCount;\n        long smallUp;\n        long bigDown;\n        boolean empty;\n\n\n        SmallSplittedLongs(int size) {\n            smalls = new long[size];\n            bigs = new long[size];\n            empty = true;\n        }\n\n        public void dropBigs() {\n            bigCount = 0;\n            if (smallCount == 1) {\n                smallCount = 0;\n                --lowerCount;\n                empty = true;\n                handleSingleValue(smalls[0]);\n                return;\n            }\n            int nt = smallCount / 2;\n            quickSelectInSmall(nt - 1);\n            bigCount = 0;\n            bigDown = smalls[nt];\n            for (int i = nt; i < smallCount; ++i) {\n                bigs[bigCount++] = smalls[i];\n                if (smalls[i] < bigDown) bigDown = smalls[i];\n            }\n            lowerCount += nt - smallCount;\n            smallCount = nt;\n            smallUp = smalls[nt - 1];\n        }\n\n\n        public void dropSmalls() {\n            lowerCount -= smallCount;\n            wantedPos -= smallCount;\n            smallCount = 0;\n\n            if (bigCount == 1) {\n                bigCount = 0;\n                empty = true;\n                handleSingleValue(bigs[0]);\n                return;\n            }\n\n            smallCount = bigCount;\n            long[] t = smalls;\n            smalls = bigs;\n            bigs = t;\n\n            int nt = smallCount / 2;\n            quickSelectInSmall(nt - 1);\n            bigCount = 0;\n            bigDown = smalls[nt];\n            for (int i = nt; i < smallCount; ++i) {\n                bigs[bigCount++] = smalls[i];\n                if (smalls[i] < bigDown) bigDown = smalls[i];\n            }\n            lowerCount += nt;\n            smallCount = nt;\n            smallUp = smalls[nt - 1];\n        }\n\n        public long getWanted() {\n            int wanted = (int) wantedPos;\n            if (smallCount >= wanted) {\n                quickSelectInSmall(wanted - 1);\n                return smalls[wanted - 1];\n            }\n            wanted -= smallCount;\n            smalls = bigs;\n            smallCount = bigCount;\n            quickSelectInSmall(wanted - 1);\n            return smalls[wanted - 1];\n        }\n\n\n        public void addForce(long l) {\n            if (empty) {\n                smalls[smallCount++] = l;\n                ++lowerCount;\n                smallUp = l;\n                empty = false;\n                return;\n            }\n            addOne(l);\n        }\n\n        public void addPair(long a, long b) {\n            if (empty) {\n                addFirstPair(Math.min(a, b), Math.max(a, b));\n                return;\n            }\n            addOne(a);\n            addOne(b);\n        }\n\n\n        private Random rnd = new Random(1442);\n\n        private void quickSelectInSmall(int t) {\n            int down = 0;\n            int up = smallCount;\n            while (up - down > 1) {\n                long pivotVal = smalls[down + rnd.nextInt(up - down)];\n                int store1 = down;\n                for (int i = down; i < up; ++i) {\n                    if (smalls[i] < pivotVal) {\n                        swap(i, store1++);\n                    }\n                }\n                if (store1 > t) {\n                    up = store1;\n                    continue;\n                }\n                int store2 = store1;\n                for (int i = store1; i < up; ++i) {\n                    if (smalls[i] == pivotVal) {\n                        swap(i, store2++);\n                    }\n                }\n                if (store2 > t) return;\n                down = store2;\n\n            }\n        }\n\n        private void swap(int a, int b) {\n            if (a == b) return;\n            long l = smalls[a];\n            smalls[a] = smalls[b];\n            smalls[b] = l;\n        }\n\n        private void addFirstPair(long min, long max) {\n            empty = false;\n            smalls[smallCount++] = min;\n            ++lowerCount;\n            smallUp = min;\n            bigs[bigCount++] = max;\n            bigDown = max;\n        }\n\n\n        private void addOne(long l) {\n            if (l < smallUp) {\n                smalls[smallCount++] = l;\n                ++lowerCount;\n                return;\n            }\n            if (l > bigDown) {\n                bigs[bigCount++] = l;\n                return;\n            }\n            if (bigCount > smallCount) {\n                smalls[smallCount++] = l;\n                ++lowerCount;\n                smallUp = l;\n                return;\n            }\n            bigs[bigCount++] = l;\n            bigDown = l;\n        }\n    }\n\n\n    public class HeapTree {\n        /*\n         * \u0445\u0440\u0430\u043D\u0438\u043C \u043F\u0430\u0440\u044B (key, value), key \\in [0, k), value - Long, \u043D\u0430 \u0441\u0442\u0430\u0440\u0442\u0435 \u0434\u043B\u044F \u0432\u0441\u0435\u0445 \u043A\u043B\u044E\u0447\u0435\u0439 \u0435\u0441\u0442\u044C \u0437\u043D\u0430\u0447\u0435\u043D\u0438\u044F\n         * \u043E\u043F\u0435\u0440\u0430\u0446\u0438\u0438:  \u0438\u0437\u043C\u0435\u043D\u0438\u0442\u044C \u0437\u043D\u0430\u0447\u0435\u043D\u0438\u0435 \u043F\u0440\u0438 \u043A\u043B\u044E\u0447\u0435, \u0443\u0434\u0430\u043B\u0438\u0442\u044C \u043A\u043B\u044E\u0447, \u043D\u0430\u0439\u0442\u0438 \u043A\u043B\u044E\u0447 \u0441 \u043C\u0438\u043D\u0438\u043C\u0430\u043B\u044C\u043D\u044B\u043C \u0437\u043D\u0430\u0447\u0435\u043D\u0438\u0435\u043C,  \u043F\u043E\u043B\u0443\u0447\u0438\u0442\u044C \u0437\u043D\u0430\u0447\u0435\u043D\u0438\u0435 \u043F\u043E \u043A\u043B\u044E\u0447\u0443\n         * \u0438\u0437\u043C\u0435\u043D\u0435\u043D\u0438\u0435 \u0438 \u0443\u0434\u0430\u043B\u0435\u043D\u0438\u0435 \u043B\u043E\u0433\u0430\u0440\u0438\u0444\u043C\u0438\u0447\u0435\u0441\u043A\u043E\u0439 \u0441\u043B\u043E\u0436\u043D\u043E\u0441\u0442\u0438, \u043F\u043E\u0438\u0441\u043A \u043A\u043E\u043D\u0441\u0442\u0430\u043D\u0442\u043D\u044B\u0439\n         *\n         * */\n        private final int size;\n        private final int[] poss;\n        private final Long[] vals;\n\n\n        HeapTree(Long[] vals) {\n            this.vals = vals;\n            this.size = vals.length;\n            this.poss = new int[size];\n            for (int i = size - 1; i >= 0; --i)\n                updateOne(i);\n        }\n\n\n        public int getMinValKey() {\n            return poss[0];\n        }\n\n        public Long getMinVal() {\n            return vals[poss[0]];\n        }\n\n        public void remove(int key) {\n            vals[key] = null;\n            update(key);\n        }\n\n        public void change(int key, long val) {\n            if (vals[key].longValue() == val) return;\n            vals[key] = val;\n            update(key);\n        }\n\n        private void updateOne(int p) {\n            poss[p] = (vals[p] == null) ? -1 : p;\n            int t = 2 * p + 1;\n            if (t < size) {\n                poss[p] = updateOne(poss[p], poss[t]);\n            }\n            ++t;\n            if (t < size) {\n                poss[p] = updateOne(poss[p], poss[t]);\n            }\n        }\n\n        private int updateOne(int p1, int p2) {\n            if (p1 == -1) return p2;\n            if (p2 == -1) return p1;\n            return (vals[p1] < vals[p2]) ? p1 : p2;\n        }\n\n\n        private void update(int p) {\n            while (true) {\n                updateOne(p);\n                if (p == 0) break;\n                p -= 1;\n                p /= 2;\n            }\n        }\n    }\n\n\n    HeapTree lowers;\n    HeapTree uppers;\n    SmallSplittedLongs ssp;\n\n    void handleSingleValue(long l) {\n        if (lowers.getMinValKey() != -1) {\n            addToSegment(lowers.getMinValKey(), l);\n        } else {\n            ssp.addForce(l);\n        }\n    }\n\n    private int[] sorted;\n\n    private class Segment {\n        final long multipier;\n        final int from;\n        final int to;\n        Long addition;\n\n        Segment(long multipier, int from, int to) {\n            this.multipier = multipier;\n            this.from = from;\n            this.to = to;\n            addition = null;\n        }\n\n\n        long minVal() {\n            long mv = (multipier > 0) ? sorted[from] * multipier : sorted[to] * multipier;\n            return addition == null ? mv : Math.min(addition, mv);\n        }\n\n        long maxVal() {\n\n            long mv = (multipier > 0) ? sorted[to] * multipier : sorted[from] * multipier;\n            return addition == null ? mv : Math.max(addition, mv);\n        }\n\n        int count() {\n            return to - from + 1 + (addition == null ? 0 : 1);\n        }\n\n        public Segment[] split() {\n            //count()>=3, from -to + 1  >= 2\n            Segment[] ret = new Segment[2];\n            int mid = (from + to) / 2;\n            if (multipier >= 0) {\n                ret[0] = new Segment(multipier, from, mid);\n                ret[1] = new Segment(multipier, mid + 1, to);\n            } else {\n                ret[1] = new Segment(multipier, from, mid);\n                ret[0] = new Segment(multipier, mid + 1, to);\n            }\n            if (addition != null) {\n                if (ret[0].maxVal() >= addition) {\n                    ret[0].addSingle(addition);\n                } else {\n                    ret[1].addSingle(addition);\n                }\n            }\n            return ret;\n        }\n\n        public void addSingle(long v) {\n            if (addition == null) {\n                addition = v;\n            } else {\n                ssp.addPair(addition, v);\n                addition = null;\n            }\n        }\n    }\n\n\n    private class SegmentPair {\n        Segment lower;\n        Segment upper;\n\n        SegmentPair(long multipier, int from, int to) {\n            Segment s = new Segment(multipier, from, to);\n            Segment[] spl = s.split();\n            lower = spl[0];\n            upper = spl[1];\n        }\n    }\n\n\n    List<SegmentPair> segmentPairs = new ArrayList<>();\n\n    private void addToSegment(int segmentPairNum, long value) {\n        SegmentPair p = segmentPairs.get(segmentPairNum);\n        long smallUp = p.lower.maxVal();\n        if (value < smallUp) {\n            lowerCount -= p.lower.count();\n            p.lower.addSingle(value);\n            lowerCount += p.lower.count();\n\n        } else {\n            p.upper.addSingle(value);\n        }\n        lowers.change(segmentPairNum, p.lower.maxVal());\n        uppers.change(segmentPairNum, -p.upper.minVal());\n    }\n\n\n    private void resplitSegment(int key, SegmentPair sp, Segment toSplit) {\n        int cnt = toSplit.count();\n        if (cnt == 1) {\n            lowers.remove(key);\n            uppers.remove(key);\n            handleSingleValue(toSplit.maxVal());\n            return;\n        }\n\n        if (cnt == 2) {\n            lowers.remove(key);\n            uppers.remove(key);\n            ssp.addPair(toSplit.minVal(), toSplit.maxVal());\n            return;\n        }\n        Segment[] spl = toSplit.split();\n        sp.lower = spl[0];\n        sp.upper = spl[1];\n        lowerCount += sp.lower.count();\n        lowers.change(key, sp.lower.maxVal());\n        uppers.change(key, -sp.upper.minVal());\n\n    }\n\n\n    private void dropFromLower(int key) {\n        SegmentPair sp = segmentPairs.get(key);\n        lowerCount -= sp.lower.count();\n        wantedPos -= sp.lower.count();\n        resplitSegment(key, sp, sp.upper);\n    }\n\n    private void dropFromLower() {\n        if (ssp.empty) {\n            dropFromLower(lowers.getMinValKey());\n        } else {\n            long v1 = lowers.getMinVal();\n            long v2 = ssp.smallUp;\n            if (v2 < v1) {\n                ssp.dropSmalls();\n            } else {\n                dropFromLower(lowers.getMinValKey());\n            }\n        }\n    }\n\n\n\n    private void dropFromUpper(int key) {\n        SegmentPair sp = segmentPairs.get(key);\n        lowerCount -= sp.lower.count();\n        resplitSegment(key,sp, sp.lower);\n    }\n\n    private void dropFromUpper(){\n        if(ssp.empty) {\n            dropFromUpper(uppers.getMinValKey());\n        }else{\n            long v1 = - uppers.getMinVal();\n            long v2 = ssp.bigDown;\n            if(v2>v1) {\n                ssp.dropBigs();\n            }else {\n                dropFromUpper(uppers.getMinValKey());\n            }\n        }\n    }\n\n    void prepareStateProcess(int[] first, int[] second) {\n        sorted = first;\n        int k = second.length;\n        ssp = new SmallSplittedLongs(2*k);\n        Long[] l1 = new Long[k];\n        Long[] l2 = new Long[k];\n\n        for(int i = 0; i<k; ++i) {\n            SegmentPair sp = new SegmentPair(second[i], 0, first.length-1);\n            segmentPairs.add(sp);\n            l1[i] = sp.lower.maxVal();\n            l2[i] = -sp.upper.minVal();\n            lowerCount += sp.lower.count();\n        }\n        lowers = new HeapTree(l1);\n        uppers = new HeapTree(l2);\n    }\n\n    long stateProcess() {\n        while(uppers.getMinValKey() != -1) {\n            if(lowerCount<wantedPos){\n                dropFromLower();\n            }else{\n                dropFromUpper();\n            }\n        }\n        return ssp.getWanted();\n    }\n\n\n\n    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {\n        if (nums1.length * 1L* nums2.length < 10) {\n            return simpleBrute(nums1, nums2, k);\n        }\n\n        if (nums1.length > nums2.length) {\n            prepareStateProcess(nums1, nums2);\n        } else {\n            prepareStateProcess(nums2, nums1);\n        }\n        wantedPos = k;\n        return stateProcess();\n\n    }\n\n    private long simpleBrute(int[] nums1, int[] nums2, long k) {\n        List<Long> finState = new ArrayList<>();\n        for (int i : nums1)\n            for (int j : nums2)\n                finState.add(i * 1L * j);\n        Collections.sort(finState);\n        return finState.get((int) (k - 1));\n    }\n\n}\n```
['Heap (Priority Queue)', 'Quickselect', 'Java']