You are given an array nums of size n and q queries. Now for each query of the form l, r and k, output the kth smallest number in sub-array between l and r.
 
Example 1:
Input: nums = {4, 1, 2, 2, 3},
Query = {{1, 5, 2}, {3, 5, 3}}
Output: {2, 3}
Explanation: For the 1st query 2nd smallest in
[1, 5] is 2. For the 2nd query 3rd smallest in
[3, 5] is 3.
Example 2:
Input: nums = {1, 2, 3, 4, 5},
Query = {{2, 5, 1}}
Output: {2}
Explanation: The 1st smallest in [2, 5] is 2.
 
Your Task:
You don't need to read or print anyhting. Your Task is to complete the function FindQuery() which takes nums and Query as input parameter and returns a list containing kth smallest for every query.
 
Expected Time Complexity: O(nlog(n))
Expected Space Complexity: O(n)
 
Constraints:
1 <= n <= 15000
1 <= nums[i] <= n
1 <= no. of queries <= 10^{4}
1 <= l <= r <= n
1 <= k <= r-l+1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Segment trees revisited

Starter code: #User function Template for python3

class Solution:
	def FindQuery(self, nums, Query):
		# Code here

Solutions:
class Solution:

	def FindQuery(self, z, Query):
		dp = {}

		def sort(i, j):
			m = (i + j) // 2
			a = i
			b = m + 1
			z = []
			while a <= m and b <= j:
				if x[a] <= x[b]:
					z.append(x[a])
					a += 1
				else:
					z.append(x[b])
					b += 1
			z += x[a:m + 1] + x[b:j + 1]
			dp[i, j] = z
			x[i:j + 1] = z

		def merge(i, j):
			if i == j:
				dp[i, i] = [x[i]]
				return
			m = (i + j) // 2
			merge(i, m)
			merge(m + 1, j)
			sort(i, j)

		def f(i, j, ii, jj, k):
			if len(dp[i, j]) == 1:
				return dp[i, j][0]

			def binse_1(x, e):
				i = 0
				j = len(x) - 1
				ans = -1
				while i <= j:
					m = (i + j) // 2
					if x[m] >= e:
						ans = m
						j = m - 1
					else:
						i = m + 1
				return ans

			def binse_2(x, e):
				i = 0
				j = len(x) - 1
				ans = -1
				while i <= j:
					m = (i + j) // 2
					if x[m] <= e:
						ans = m
						i = m + 1
					else:
						j = m - 1
				return ans
			m = (i + j) // 2
			aaa = binse_1(dp[i, m], ii)
			bbb = binse_2(dp[i, m], jj)
			size = 0 if aaa == -1 or bbb == -1 else bbb - aaa + 1
			if k <= size:
				return f(i, m, ii, jj, k)
			else:
				return f(m + 1, j, ii, jj, k - size)
		l = len(z)
		x = [(z[i], i) for i in range(l)]
		x.sort()
		x = [x[i][1] for i in range(l)]
		merge(0, l - 1)
		res = []
		for (i, j, k) in Query:
			res.append(z[f(0, l - 1, i - 1, j - 1, k)])
		return res