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<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.
If your solution works, then running time is $$$O(q*log^2(n))$$$ and memory usage is $$$O(n*log(n))$$$.
Why? You are using Merge Sort Tree. The height is $$$log(n)$$$, so each number will enter exactly $$$log(n)$$$ times. Search for required nodes, as well as the usual Segment Tree, works in $$$O(log(n))$$$, and in each "good" node we are looking for an answer for $$$O(log(n))$$$ with binary search in the worst case.
But for it to work exactly in $$$O(q*log^2(n))$$$, you need to do the correct merge(): namely, transfer vectors to the function ($$$merge(vector<int> &a, vector<int> &b)$$$) and work using pointers ($$$--pa$$$, $$$if x <= y$$$ and vice versa).
Sorry for using google translator.
Thanks a lot.