ABC379F Buildings 2 题解
刘梓轩2010
·
·
题解
纪念第一道在场上想出正解但没写出的 F 题。
题意
有 n 栋大楼排成一排，给你 q 次询问，每次给出 l 和 r，问你在 r 之后有多少栋大楼可以被 l 到 r 之间的大楼看到，定义两个楼能看到当且仅当它们之间没有比右边的楼更高的楼。
## 思路
首先想到 $l$ 到 $r$ 之间的楼能向后看到的楼一定是一个单调不减的序列，而且一定是最靠近 $r$ 的单调不减的序列，否则就会互相遮挡看不见。
然后我们发现，能向后看到的楼的高度一定大于等于区间内的最大值，否则最大值左边的楼就看不见这栋楼了。如果最大值在最左边，那就要大于 $l+1$ 到 $r$ 之间的最大值。
所以我们先用单调栈倒序维护以每个点为开头的最近的单调不减序列的长度，记为 $ans_i$，用线段树找到区间内的最大值，然后可以用线段树二分找到 $r$ 之后的第一个大于最大值的楼的位置，记为 $pos$，$ans_{pos}$ 即为答案。
如果还没理解可以画图，或结合下面代码食用。
## Code
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
struct Node
{
int l,r,val;
}tr[N<<2];
int n,q;
int a[N];
int ans[N];
inline void pushup(int rt)
{
tr[rt].val=max(tr[rt<<1].val,tr[rt<<1|1].val);
}
void build(int rt,int l,int r)
{
tr[rt].l=l,tr[rt].r=r;
if(l==r)
{
tr[rt].val=a[l];
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
int qry1(int rt,int l,int r)
{
if(l<=tr[rt].l&&tr[rt].r<=r)
{
return tr[rt].val;
}
int mid=(tr[rt].l+tr[rt].r)>>1;
int res=-inf;
if(l<=mid) res=max(res,qry1(rt<<1,l,r));
if(r>mid) res=max(res,qry1(rt<<1|1,l,r));
return res;
}
pair<int,int> qry2(int rt,int l,int r,int val)
{
if(tr[rt].l==tr[rt].r)
{
return {tr[rt].val,tr[rt].l};
}
int mid=(tr[rt].l+tr[rt].r)>>1;
if(l<=tr[rt].l&&tr[rt].r<=r)
{
if(tr[rt<<1].val>=val) return qry2(rt<<1,l,r,val);
else return qry2(rt<<1|1,l,r,val);
}
if(l<=mid)
{
pair<int,int> p=qry2(rt<<1,l,r,val);
if(p.fi>=val) return p;
}
if(r>mid) return qry2(rt<<1|1,l,r,val);
}
stack<int> st;
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int i=n;i>=1;i--)
{
while(!st.empty()&&st.top()<a[i]) st.pop();
st.push(a[i]);
ans[i]=st.size();
}
while(q--)
{
int l,r;
cin>>l>>r;
if(r==n)
{
cout<<0<<endl;
continue;
}
int maxn=qry1(1,l,r);
if(a[l]==maxn) maxn=qry1(1,l+1,r);
if(qry1(1,r+1,n)<maxn)
{
cout<<0<<endl;
continue;
}
cout<<ans[qry2(1,r+1,n,maxn).se]<<endl;
}
return 0;
}
```