Hello, I have tried a lot to solve [MKTHNUM-spoj](https://www.spoj.com/problems/MKTHNUM/). For solving this , I have slightly changed the problem statement, it goes like this : ↵
↵
**you are asked to find a number such that there are k-1 numbers less than that in range [l...r]**↵
↵
Then I made a **merge sort tree** and sorted the initial array and **Binary Searched** it. My time complexity is : $O((log2(n))^2)$ . I am getting **Runtime Error** in case 11 (i think). But couldn't find the bug :'( .↵
here goes my code : ↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define all(v) v.begin(),v.end()↵
using namespace std;↵
↵
const int N = 100099;↵
vector<int>tree[N*3];↵
int ara[N+12];↵
↵
void build(int at ,int l,int r)↵
{↵
if(l == r){↵
tree[at].push_back(ara[l]);↵
return;↵
}↵
int mid = (l+r)/2;↵
build(at*2,l,mid);↵
build(at*2+1,mid+1,r);↵
↵
merge(all(tree[at*2]),all(tree[at*2+1]),back_inserter(tree[at]));↵
}↵
↵
int query(int at,int L,int R,int l,int r,int indx)↵
{↵
if(l > R or r < L)return 0;↵
if(L >= l and r >= R){↵
int pp = upper_bound(all(tree[at]),ara[indx])-tree[at].begin();↵
return pp;↵
}↵
int mid = (L+R)/2;↵
return query(at*2,L,mid,l,r,indx) + query(at*2+1,mid+1,R,l,r,indx);↵
}↵
↵
int main()↵
{↵
int n,q,l,r,k;↵
scanf("%d%d",&n,&q);↵
for(int i= 1; i <= n;i++){↵
scanf("%d",&ara[i]);↵
}↵
build(1,1,n);↵
sort(ara+1,ara+1+n);↵
while(q--){↵
scanf("%d%d%d",&l,&r,&k);↵
int high = n,low = 1,mid,ans = -1;↵
int cnt = 0;↵
while(low <= high){↵
mid = (low+high)/2;↵
int pp = query(1,1,n,l,r,mid);↵
if(k <= pp){↵
ans = mid;↵
high = mid-1;↵
}↵
else low = mid+1;↵
}↵
printf("%d\n",ans);↵
} ↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
**you are asked to find a number such that there are k-1 numbers less than that in range [l...r]**↵
↵
Then I made a **merge sort tree** and sorted the initial array and **Binary Searched** it. My time complexity is : $O((log2(n))^2)$ . I am getting **Runtime Error** in case 11 (i think). But couldn't find the bug :'( .↵
here goes my code : ↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#define all(v) v.begin(),v.end()↵
using namespace std;↵
↵
const int N = 100099;↵
vector<int>tree[N*3];↵
int ara[N+12];↵
↵
void build(int at ,int l,int r)↵
{↵
if(l == r){↵
tree[at].push_back(ara[l]);↵
return;↵
}↵
int mid = (l+r)/2;↵
build(at*2,l,mid);↵
build(at*2+1,mid+1,r);↵
↵
merge(all(tree[at*2]),all(tree[at*2+1]),back_inserter(tree[at]));↵
}↵
↵
int query(int at,int L,int R,int l,int r,int indx)↵
{↵
if(l > R or r < L)return 0;↵
if(L >= l and r >= R){↵
int pp = upper_bound(all(tree[at]),ara[indx])-tree[at].begin();↵
return pp;↵
}↵
int mid = (L+R)/2;↵
return query(at*2,L,mid,l,r,indx) + query(at*2+1,mid+1,R,l,r,indx);↵
}↵
↵
int main()↵
{↵
int n,q,l,r,k;↵
scanf("%d%d",&n,&q);↵
for(int i= 1; i <= n;i++){↵
scanf("%d",&ara[i]);↵
}↵
build(1,1,n);↵
sort(ara+1,ara+1+n);↵
while(q--){↵
scanf("%d%d%d",&l,&r,&k);↵
int high = n,low = 1,mid,ans = -1;↵
int cnt = 0;↵
while(low <= high){↵
mid = (low+high)/2;↵
int pp = query(1,1,n,l,r,mid);↵
if(k <= pp){↵
ans = mid;↵
high = mid-1;↵
}↵
else low = mid+1;↵
}↵
printf("%d\n",ans);↵
} ↵
}↵
~~~~~↵
↵
↵
