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

My 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 a , vector b ){

vector 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.