K-th Number | Editorial by sirjan13

The key idea is to build a Segment Tree with a vector at every node and the vector contains all the elements of the sub-range in a sorted order. And if we observe this segment tree structure this is somewhat similar to the tree formed during the merge sort algorithm(that is why it is called merge sort tree)

We use same implementation as discussed in Merge Sort Tree (Smaller or equal elements in given row range)

Firstly, we maintain a vector of pairs where each pair {value, index} is such that first element of pair represents the element of the input array and the second element of the pair represents the index at which it occurs.

Now we sort this vector of pairs on the the basis of the first element of each pair.

After this we build a Merge Sort Tree where each node has a vector of indices in the sorted range.

When we have to answer a query we find if the Kth smallest number lies in the left sub-tree or in the right sub-tree. The idea is to use two binary searches and find the number of elements in the left sub-tree such that that the indices lie within the given query range.
Let the number of such indices be M.

If M>=K, it means we will be able to find the Kth smallest Number in the left sub-tree thus we call on the left sub-tree.

Else the Kth smallest number lies in the right sub-tree but this time we don’t have to look for the Kth smallest number as we already have first M smallest numbers of the range in the left sub-tree thus we should look for the remaining part ie the (K-M)th number in the right sub-tree.

This is the Index of Kth smallest number the value at this index is the required number.

```
#include <bits/stdc++.h>

//____By:sirjan13____

#define ll long long int
#define mod 1000000007
#define show(a) for(int i=0;i<a.size();i++) cout<<a[i]<<" ";
#define fi first
#define se second
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long int>
#define pb push_back
#define pi pair<int,int>
#define si set<int>
#define sll set<ll>
#define maxheap priority_queue<int>
#define minheap priority_queue<int,vector<int>,greater<int>>
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fast_io() cin.sync_with_stdio(false);cout.sync_with_stdio(false);
#define long_zero 0ll
#define long_one 1ll
#define N 100015

inline int sbt(int x){return __builtin_popcount(x);}

using namespace std;

int n,q,mem[N+5];
vector<pi> a;

vi tree[4*N+5];

void build(int l,int r,int i){
 if(l==r){
 tree[i].pb(a[l].se);
 return;
 }
 int mid=(l+r)/2;
 build(l,mid,2*i);
 build(mid+1,r,2*i+1);
 merge(all(tree[2*i]),all(tree[2*i+1]),back_inserter(tree[i]));
}
int query(int ss,int se,int qs,int qe,int i,int k){
 if(ss==se){
 return tree[i][0];
 }
 int mid=(ss+se)/2;
 int less_than_qe = (upper_bound(all(tree[2*i]),qe)-tree[2*i].begin());
 int greater_than_qs = (lower_bound(all(tree[2*i]),qs)-tree[2*i].begin());
 int segment_qs_to_qe = (less_than_qe - greater_than_qs);
 if(segment_qs_to_qe >= k){
 return query(ss,mid,qs,qe,2*i,k);
 }
 else{
 return query(mid+1, se, qs, qe, 2*i+1, k-segment_qs_to_qe);
 }
}
int main() {
 fast_io()
 cin>>n>>q;
 for(int i=0;i<n;i++){
 cin>>mem[i];
 a.pb(mp(mem[i],i));
 }
 sort(all(a));
	build(0,n-1,1);
	while(q--){
	 int l,r,k;
	 cin>>l>>r>>k;
	 cout<<mem[query(0,n-1,l-1,r-1,1,k)]<<endl;
	}
	return 0;
}

```

K-th Number | Editorial by sirjan13

Download submission

All caught up!

View submission

Is your resume even shortlisted?