Could anyone help me make my solution for MKTHNUM faster?

problem link: https://www.spoj.com/problems/MKTHNUM/6

So I’ve recently solved the MKTHNUM problem. I firstly tried to use a merge sort segment tree but immediately realized that it would be too inefficient so I switched to a persistent segment tree approach ( N*LogN) that obtained a total time of 2.44 seconds. This is enough to pass all the tests, but I couldn’t help myself from noticing that almost everyone had a much better time than mine, despite the fact that I tried to use one of the best algorithms for it. I also tried to use the same code for an almost identical problem from another site, and this time I was actually getting TLE for the last 2 tests.

I hope that I changed most of the variables from my native language to English, if not, I’m really sorry. Could anyone please make me understand how I can make this algorithm faster? (also please don’t judge the memory leaks, I know I should usually deal with them).

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <unordered_map>
using namespace std;
ifstream in(“kth.in”);
ofstream out(“kth.out”);

class vertex
{
public:
vertex(){}
vertex(int nr){ val = nr;}
vertex(vertex* n1, vertex* n2)
{
val = n1->val + n2-> val;
left = n1;
right = n2;
}

int val = 0;
vertex *left = nullptr, *right = nullptr;

};
int idn = 0, idr = 1;
int n, m;
vector<vertex*> roots;
int a[300001], b[300001];
unordered_map<int, int> valid, idval;

vertex* build(int st, int dr);
vertex* update(vertex* n1, int poz, int st, int dr);
int query(vertex* n1, vertex* n2, int st, int dr, int poz);
int main()
{

cin >> n >> m;
for ( int i = 1; i <= n; ++i )
    cin >> b[i], a[i] = b[i];

sort(b + 1, b + n + 1);

for ( int i = 1; i <= n; ++i )
{
if ( valid[b[i]] == 0 )
valid[b[i]] = ++idn, idval[valid[b[i]]] = b[i];
}
roots.emplace_back(new vertex(0));
roots.emplace_back(build(1, idn));
for ( int i = 1; i <= n; ++i )
{
roots.emplace_back(update(roots[idr], valid[a[i]], 1, idn));
idr++;
}

for ( int i = 1; i <= m; ++i )
{
int st, dr, k;
cin >> st >> dr >> k;
cout << idval[query(roots[dr + 1], roots[st], 1, idn, k)] << “\n”;
}
for ( auto c:roots )
delete c;
return 0;
}

vertex* build(int st, int dr)
{
if ( st == dr )
return new vertex(0);
int mij = ( st + dr )/2;
return new vertex(build(st, mij), build( mij + 1, dr));

}

vertex* update(vertex* n1, int poz, int st, int dr)
{
if ( st == dr )
return new vertex(n1->val + 1);

  int mij = ( st + dr )/2;
  if ( poz <= mij )
    return new vertex(update(n1 -> left, poz, st, mij), n1 -> right);
  else return new vertex(n1 -> left, update(n1 -> right, poz, mij + 1, dr));

}

int query(vertex* n1, vertex* n2, int st, int dr, int poz)
{

if (  st == dr )
{
    return st;
}
int mij = ( st + dr )/2;
if ( n1->left == nullptr or n2->left == nullptr )
    cout << "vai";
int poz2 = n1->left->val - n2->left->val;

if ( poz2 >= poz )
    return query(n1->left, n2->left, st, mij, poz);
return query(n1-> right, n2->right, mij + 1, dr, poz - poz2);

}