题解：P14989 传送

· · 题解

P14989 传送 题解

天哪竟然场切了，猫猫留下了欣慰的泪水 /ll

题意

给定 p_{1 \sim n}，每个点可以往自己左面第一个值比它大的点跳（后面简称这个点为“目标点”），右面也可以，然后 q 次询问，每次给定 k 个点的下标，问它们能跳到的点中公共的有多少个。

一定要分清值和下标，因为我赛时因为这个浪费了一个小时呜呜。

思路

看到跳公共点第一想法是 LCA 吧，不会的参见这里，所有的 k 加起来是 \le 5 \times 10^5 的所以暴力枚举 k 然后两两依次求 LCA 就可以了，最坏 O(\sum k \times \log n)。那怎么建树呢？

一、找目标点

我们首先处理怎么找到每个点左面或右面的目标点，这个貌似是单调栈板子，不会的参见这里，从左往右遍历求左目标点，从右往左遍历求右目标点，中间记得清空栈。初始化完了，得到两个数组 lp_i 和 rp_i 存储每个点左右目标点的值！是值！（放下标说不定也行，别的题解应该会有讲的）。

二、贪心

其次，每个点左右都能跳，这让我们很头疼。但是仔细想想，其实只用往两边目标点的值最小的那一边跳就可以了，证明一下。

设当前点是 p_i，左右目标点分别为 p_l 和 p_r，由题意得 p_l>p_i 且 p_r>p_i。而又因为这两个点都是第一个值大于 p_i 的点，所以 (p_{l+1} \sim p_{i-1})<p_i 且 (p_{i+1} \sim p_{r-1})<p_i，所以 p_l 和 p_r 比 p_{l+1} \sim p_{r-1} 都大。所以当 i 跳到 \min(l,r) 时，一定会往 \max(l,r) 跳，而答案要求公共点数量越多越好，所以跳 \min(l,r) 比跳 \max(l,r) 更优。（有疏漏请指出，其实赛时是猜的）

三、建树

所以每个点都只能往一个点跳了。这回好建树了。在每个点的值 p_i 和 \min(lp_i,rp_i) 之间建边就好了，我建的双向。注意这是一棵值树。

四、LCA

首先，把输入的 k 个下标转换成值。因为建的是值树。每次 LCA 两个点的值，求出来最近的公共点。答案让求有多少个公共点所以该最近点在树上的深度就是公共点数量，因为既然公共到这个点了一定可以继续往上爬到树根。

剩余亿点细节放注释里了，祝您阅读愉快。

Code

成功抢到最劣解。

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=5e5+5,logn=20,inf=0x3f3f3f3f3f3f3f3f;
int n,q,p[N],pre[N],cur;
int dep[N],fa[N]; // dep是深度，fa是父节点，用来ST表
int lp[N],rp[N];
int st[N][25]; // ST表
stack<int> s; // 单调栈
struct edge // 链式前向星存图
{
    int l,r,nxt;
    void ae(int u,int v) // 加边
    {l=u,r=v,nxt=pre[u],pre[u]=cur;}
}e[N*2];

void dfs(int x,int f) // 用来求每个点深度+父节点
{
    fa[x]=f,dep[x]=dep[f]+1;
    for(int i=pre[x];i;i=e[i].nxt)
    {
        int r=e[i].r;
        if(r==f)
            continue;
        dfs(r,x);
    }
}

void set_st() // LCA板子
{
    for(int i=1;i<=n;i++)
        st[i][0]=fa[i];
    for(int j=1;j<=logn;j++)
        for(int i=1;i<=n;i++)
            st[i][j]=st[st[i][j-1]][j-1];
}

int lca(int x,int y) // LCA板子
{
    if(dep[x]<dep[y])
        swap(x,y);
    for(int j=logn;j>=0;j--)
        if(dep[st[x][j]]>=dep[y])
            x=st[x][j];
    if(x==y)
        return x;
    for(int j=logn;j>=0;j--)
        if(st[x][j]!=st[y][j])
            x=st[x][j],y=st[y][j];
    return fa[x];
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    // 不加优化容易爆 TLE，见后文 Update 内容
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<=n;i++) // 单调栈求左目标点
    {
        while(!s.empty() && p[s.top()]<=p[i])
            s.pop();
        lp[i]=s.empty() ? inf : p[s.top()];
        // 存的是值！！所以用p[]包起来
        // 栈空代表没有左目标点，放最大值（因为建树时取的lp rp的min）
        s.push(i);
    }
    while(!s.empty()) // 记得清空！
        s.pop();
    for(int i=n;i>0;i--) // 右目标点
    {
        while(!s.empty() && p[s.top()]<=p[i])
            s.pop();
        rp[i]=s.empty() ? inf : p[s.top()];
        // 同上，放值
        s.push(i);
    }
    for(int i=1;i<=n;i++)
    {
        int minn=min(lp[i],rp[i]); // 取min
        if(minn!=inf) // 如果==inf说明左右都没有目标点，那建不了边
        {
            e[++cur].ae(minn,p[i]);
            e[++cur].ae(p[i],minn); // 双向
        }
    }
    dfs(n,0); // 一定先dfs再建ST表！不然没有每个点的父节点
    set_st(); // 建ST表
    while(q--)
    {
        int k,now;
        cin>>k>>now;
        now=p[now]; // 换成值！！！
        if(k==1) // 只有它一个点就直接输出深度
        {
            cout<<dep[now]<<'\n';
            continue;
        }
        // 现在，now的身份是当前的最近公共祖先
        for(int i=2;i<=k;i++)
        {
            int x;
            cin>>x;
            x=p[x]; // 换成值！！！
            now=lca(now,x); // 之前求好的祖先和新进的点求一次lca，更新当前祖先
        }
        cout<<dep[now]<<'\n'; // 输出求好的祖先的深度
        // while(q--)这一部分如果没听懂回复文章问我，我基本在线
    }
    return (0.0);
}

给我赞赞 qwq

Update

2026.1.19 发现代码的一处 RE 错误，我在赛后优化代码时笔误。

2026.1.19 加入输入输出优化，因为赛时没写优化 993ms 卡过了赛后发现 TLE 然后紧急加上。

2026.1.20 发现一处时间复杂度计算错误，太糖了，已更正。