#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxl = 20;
const int maxn = 100010;
const int inf = 1000000010;
class SparseTable
{
public:
void build(int n, vector<int> v, bool mn = false)
{
isMin = mn;
for(int i = 1 ; i <= n ; i++)
tab[0][i] = (mn ? -v[i] : v[i]);
for(int k = 1 ; k < maxl ; k++)
for(int i = 1 ; i + (1 << k) - 1 <= n ; i++)
tab[k][i] = max( tab[k - 1][i] , tab[k - 1][i + (1 << (k - 1))] );
}
int query(int l, int r)
{
if( l > r )
return (isMin ? inf : -inf);
int t = 31 - __builtin_clz(r - l + 1);
int ans = max( tab[t][l] , tab[t][r - (1 << t) + 1] );
return (isMin ? -ans : ans);
}
protected:
bool isMin;
int tab[maxl][maxn];
};
int n;
int v[maxn];
bool hasBuilt = false;
SparseTable stV, stR, stL, corner;
vector<int> valleys, optL, optR, cL, cR;
bool isValid(int i, int j, int D)
{
int peak = stV.query( i + 1 , j - 1 );
if( v[i] <= peak - D && v[j] <= peak - D )
return true;
return false;
}
int findOptL(int i, int D)
{
int l = 1, r = i - 1;
if( v[i] > stV.query( l , i - 1 ) - D )
return 0;
while( l < r )
{
int m = ( l + r )/2;
if( l == r - 1 ) m = r;
if( v[i] <= stV.query( m , i - 1 ) - D )
l = m;
else
r = m - 1;
}
return l;
}
int findOptR(int i, int D)
{
int l = i + 1, r = n;
if( v[i] > stV.query( i + 1 , r ) - D )
return n + 1;
while( l < r )
{
int m = ( l + r )/2;
if( v[i] <= stV.query( i + 1 , m ) - D )
r = m;
else
l = m + 1;
}
return r;
}
void buildHistogram(int D)
{
optL.resize( n + 1 );
optR.resize( n + 1 );
for(int i = 1 ; i <= n ; i++)
{
optL[i] = findOptL(i, D);
optR[i] = findOptR(i, D);
}
}
void build(int D)
{
buildHistogram(D);
stR.build( n , optR , true );
stL.build( n , optL );
// Corner Case
cL.resize( n + 1 , 0 );
cR.resize( n + 1 , n + 1 );
for(int i = 1 ; i <= n ; i++)
{
cL[ optR[i] ] = min( cL[ optR[i] ] , i );
cR[ optL[i] ] = min( cR[ optL[i] ] , i );
}
vector<int> tmp(n + 1, n + 1);
for(int i = 1 ; i <= n ; i++)
tmp[ cL[i] ] = min( tmp[ cL[i] ] , cR[i] );
corner.build( n , tmp );
//
for(int i = 1 ; i <= n ; i++)
{
while( !valleys.empty() )
{
int j = valleys.back();
if( isValid( j , i , D ) )
{
valleys.push_back( i );
break;
}
if( v[j] < v[i] )
break;
valleys.pop_back();
}
if( valleys.empty() )
valleys.push_back( i );
}
hasBuilt = true;
}
void init(int N, vector<int> H) {
n = N;
H.insert( H.begin() , 0 );
for(int i = 1 ; i <= n ; i++)
v[i] = H[i];
stV.build( n , H );
}
bool newPairL(int L, int opt)
{
int l = L, r = optL[opt] - 1;
if( stR.query( l , r ) < opt )
return true;
return false;
}
bool newPairR(int R, int opt)
{
int l = optR[opt] + 1, r = R;
if( opt < stL.query( l , r ) )
return true;
return false;
}
int max_towers(int L, int R, int D)
{
if( !hasBuilt )
build( D );
L++; R++;
if( R - L + 1 <= 2 )
return 1;
int pL = lower_bound( valleys.begin() , valleys.end() , L ) - valleys.begin();
int pR = upper_bound( valleys.begin() , valleys.end() , R ) - valleys.begin();
if( pL == pR )
{
if( corner.query( L , R ) <= R )
return 2;
return 1;
}
int ans = pR - pL;
if( newPairL( L , valleys[pL] ) )
ans++;
if( newPairR( R , valleys[pR - 1] ) )
ans++;
return ans;
}
