ABC379Fsol

Xuan_tmp · 2024-11-11 20:57:00 · 题解

upd：修正了原文与注释的一点细节错误和示意图错误。

这里提供一种不需要高级数据结构的在线做法。

我们发现每个点向右看能看到的，且比自己高的建筑数量是可以用单调栈线性求的，可以先预处理出来，设为 rs_i。然后我们考虑询问：

对于每一个询问，考虑 l+1 到 r 这些建筑的高度最大值，设为 h_{max}，这可以很轻松地用 ST 表求出来。

如果 h_{max}=h_r，那么 l 向右看到的建筑是 r 向右看到的且不比 r 低的建筑序列前面加上 l+1 到 r 中看到的建筑所得到的序列，此时容易知道答案为 rs_r。

但如果 h_{max}>h_r 呢？

我们看一张示意图：

我们发现，答案所求长度的序列一定是 r 看到的建筑序列的后缀，而该后缀的首个建筑的高度恰好大于等于 h_{max}。

所以我们的问题就变成了：在 r 看到的建筑序列中，找到第一个高度大于等于 h_{max} 的建筑。

这个问题可以使用倍增解决。记录每个建筑向右看到且不比自己低的建筑序列中，第 2^0,2^1,2^2,\dots 个建筑是哪一个。查询时直接仿照最近公共祖先的跳法，找到序列中目标后缀的前一个建筑，输出该建筑向右能看到且不低于该建筑的建筑数量即可。

这里有一个坑点，就是一定要输出目标后缀的前一个建筑对应的答案，因为一个建筑向右看到的建筑是不包含它本身的。

ACcode

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,Q,lg[200005],f[200005][20],g[200005][20];
int h[200005],rs[200005];
int R,q[200005];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>Q;lg[1]=0;
    for (int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++)cin>>h[i],f[i][0]=h[i];
    h[0]=1e9+7;//这是哨兵
    for(int i=n;i>=1;i--){
        while(R>0&&h[q[R]]<h[i])R--;//队列里存的是编号！
        rs[i]=R;
        g[i][0]=q[R];//记录右侧第一个不小于自己的
        q[++R]=i;
    }//单调栈预处理rs[i]
    for (int j=1;j<=lg[n];j++)
        for (int i=1;i<=n-(1<<j)+1;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]),
            g[i][j]=g[g[i][j-1]][j-1];//跳ST表和倍增
    while(Q--){
        int l,r;cin>>l>>r;
        l++;
        int len=lg[r-l+1];
        int mx=max(f[l][len],f[r-(1<<len)+1][len]);//区间最大值
        if(mx==h[r]){
            cout<<rs[r]<<endl;
            continue;
        }
        for(int i=18;i>=0;i--)
            if(h[g[r][i]]<mx)
                r=g[r][i];//直接跳
        cout<<rs[r]<<endl;
    }
    return 0;
}