# PROBLEM LINK:

Practice

Div-3 Contest

Div-2 Contest

Div-1 Contest

Author: Ashish Vishal, Aditya Kumar Singh

Tester: Shikhar Sharma, Daanish Mahajan

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Data structures

# PROBLEM:

Given an array of N stones each of some height.

For each query, we are given two positions and we have to output the total

number of stones visible from both positions.

# EXPLANATION:

While maintaining a stack we can easily determine the number of stones

visible from each position in linear time.

Thereafter we can calculate the height and position of the maximum stone

present between stones A and B.

It is not tough to see that the number of stones visible from this position

is also the number of stones that are visible from both positions A and B.

As for the implementation details we can use a segment Tree to determine the

maximum between A and B.

Also we maintain a map where for each height we store a pair of position

and size of stack (which corresponds to the number of visible stones from this position).

Finally we can just use lower_bound to find out the exact position of the maximum.

# SOLUTIONS:

## Setter's Solution

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define is insert

#define rep1(i,a,b) for(long long i=a;i<=b;i++)

#define F first

#define S second

#define file ifstream fin(â€śinput.txtâ€ť);ofstream fout(â€śoutput.txtâ€ť);

#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fr(n) for(long long i=0;i<n;i++)

#define rep(i,a,b) for(long long i=a;i<b;i++)

#define ALL(x) (x).begin(), (x).end()

typedef long long int ll;

typedef long double ld;

typedef vector vi;

```
ll n,m,l,r,siz;
vi h,tree,sgr;
void build_segtree()
{
tree.resize(2*siz,0);
rep(i,siz,2*siz)
tree[i]=i-siz+1;
for(int i=siz-1;i>0;i--)
{
if(h[tree[2*i]]>h[tree[2*i+1]])
tree[i]=tree[2*i];
else
tree[i]=tree[2*i+1];
}
}
ll query(ll node,ll l,ll r,ll x,ll y)
{
if(l>r || y<l || x>r)
return 0;
if(x<=l && r<=y)
return tree[node];
ll id1=query(2*node,l,(l+r)/2,x,y);
ll id2=query(2*node+1,1+(l+r)/2,r,x,y);
if(h[id1]>h[id2])
return id1;
else
return id2;
}
void right_next_gr()
{
sgr.resize(n+1,0);
stack<ll>st;
for(int i=n;i>0;i--)
{
while(!st.empty()&&h[i]>=h[st.top()])
st.pop();
if(!st.empty())
sgr[i]=1+sgr[st.top()];
st.push(i);
}
}
void solve()
{
cin>>n>>m;
siz=pow(2,ceil(log2(n)));
h.clear();
tree.clear();
sgr.clear();
h.resize(siz+1,0);
rep(i,1,n+1)cin>>h[i];
build_segtree();
right_next_gr();
fr(m)
{
cin>>l>>r;
if(l>r)
swap(l,r);
ll ind=query(1,1,siz,l,r);
cout<<sgr[ind]<<"\n";
}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.in", "r", stdin);
freopen("outputf.in", "w", stdout);
#endif
fast;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
```

## Tester's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define F first
#define S second
#define mp make_pair
////-------------------------------------------------------------------------
#define int long long ////////////
////--------------------------------------------------------------------------
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(s) (int)((s).size())
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define nl "\n"
const int N = 2e5+5;
void construct_segment_tree(vector<int>& segtree, vector<int>& a, int n)
{
for (int i = 0; i < n; i++)
segtree[n + i] = a[i];
for (int i = n - 1; i >= 1; i--)
segtree[i] = max(segtree[2 * i],
segtree[2 * i + 1]);
}
void update(vector<int>& segtree, int pos, int value, int n)
{
pos += n;
segtree[pos] = value;
while (pos > 1) {
pos >>= 1;
segtree[pos] = max(segtree[2 * pos],
segtree[2 * pos + 1]);
}
}
int range_query(vector<int>& segtree, int left, int right, int n)
{
left += n;
right += n;
int ma = INT_MIN;
while (left < right) {
if (left & 1) {
ma = max(ma, segtree[left]);
left++;
}
if (right & 1) {
right--;
ma = max(ma, segtree[right]);
}
left /= 2;
right /= 2;
}
return ma;
}
//-------------------------------------------------------------------------------
void do2win(int test)
{
int n,m; cin>>n>>m;
vi h(n);
rep(i,0,n) cin>>h[i];
vi segtree(2*n);
construct_segment_tree(segtree,h,n);
map< int, set<pii> > M;
stack<int> st;
for(int i=n-1;i>=0;i--)
{
while((!st.empty())&&(st.top()<=h[i]))
st.pop();
st.push(h[i]);
M[h[i]].insert(mp(i,sz(st)));
}
while(m--)
{
int k,l; cin>>k>>l; k--,l--;
if(k>l) swap(k,l);
int mx=range_query(segtree,k,l+1,n);
auto it=M[mx].lower_bound(mp(k,0));
pii p=*it;
int ans=p.S-1;
cout<<ans<<nl;
}
}
//-------------------------------------------------------------------------------
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt","w", stderr);
#endif
///+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
FAST;
cout<<fixed<<setprecision(20);
///+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
int test; test=1;
cin>>test;
for(int i=1;i<=test;i++)
{
do2win(i);
}
return 0;
}
```