I got this(ADATREE — Ada and Trees) problem from morass blog segment tree section. I stuck to analyzing the average complexity of this problem in the worst case for this AC solution.

///   BISMILLAHIR RAHMANIR RAHEEM
#include<bits/stdc++.h>
using namespace std;
#define MUHAMMAD        ios::sync_with_stdio(0);cin.tie(0);
#define all(x)          (x).begin(), (x).end()
using ll = long long;
const ll N = 3e5 + 5;

vector < ll > tr[N<<2];

ll n;
ll arr[N];
ll q;
ll x;

vector < ll >  merge( vector<ll> a , vector<ll> b ){

 vector<ll> order;
 while( a.size() and b.size() ){
    int x = a.back();
    int y = b.back();
    if ( x <= y ) {
            order.push_back ( x );
            a.pop_back();
    }
    else {
            order.push_back ( y );
            b.pop_back();
    }
 }

 while(a.size()) order.push_back(a.back()) , a.pop_back();
 while(b.size()) order.push_back(b.back()) , b.pop_back();
 return order;
}

void build(ll u, ll st, ll en) {

    if (st==en) {
        tr[u].push_back ( arr[st] );
    }
    else {
        ll mid = (st+en)/2;
        build(2*u, st, mid);
        build(2*u+1, mid+1, en);

        vector < ll > bame = tr[2*u];
        vector < ll > dane = tr[2*u+1];
        reverse ( all ( bame ) );
        reverse ( all ( dane ) );

        vector<ll> res = merge( bame , dane );
        reverse ( all ( res ) );
        while(res.size()){
            tr[u].push_back ( res.back() );
            res.pop_back();
        }
    }
}

ll query(ll u, ll st, ll en, ll l, ll r) {

    ll bame , dane , res;
    if (r<st || en<l)  return 0;     
    if (l<=st && en<=r){
        ll lo = st;
        ll hi = en;
        ll mx = 0;
        while(lo<=hi){
            ll mid = (lo+hi)>>1;
            ll cur = tr[u][mid-st];
            if ( cur > x ) hi = mid - 1;
            else{
                lo = mid + 1;
                mx = max ( mx , cur );
            }
        }
        return mx;
    }
    ll mid = (st+en)/2;
    bame = query(2*u, st, mid, l, r);
    dane = query(2*u+1, mid+1, en, l, r);

    return max(bame,dane);
}


void Solution ( int tc ){

  cin >> n >> q;
  for ( int i = 1 ; i <= n ; ++i ) cin >> arr[i];
  build ( 1 , 1 , n );
  for ( int i = 1 ; i <= q ; i++ ){
    ll l , r;
    cin >> l >> r >> x;
    l++;
    r++;
    ll res = query ( 1 , 1 , n , l , r );
    cout << res << "\n";
  }
  return;
}

int main()
{
   MUHAMMAD;

   int testcase = 1 , tc = 0;

    /// cin >> testcase;

    for ( int i = 1 ; i <= testcase ; ++i ){
       Solution( ++tc );
    }
    return 0;
}

/*

Explanation:

 Time :


----------------------------------------------------------------------------------------------------------------



  Alhamdulillah
*/

Can anyone help me to calculate this. Thanks in advance.