自动搬运

查看原文

来自洛谷，原作者为

	sqrtqwq 行け 決して振り向かないで /もう届かない場所へ

搬运于2025-08-24 22:35:31，当前版本为作者最后更新于2025-07-23 18:50:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑维护一个大根的笛卡尔树。那么从一颗树跳到下一棵树的操作就类似于从一个点跳到他在笛卡尔树上的一个儿子。

那么对于一个节点 $i$ 考虑去维护 $dp_i$ 表示从节点 $i$ 开始，能跳多少次即节点 $i$ 向下的最长链长度。

那么我们直接从根节点开始开始 $dp$，那么转移即为：

$$dp_u = \min(dp_{ls} - [a_{ls} = a_{u}],dp_{rs} - [a_{rs} = a_u]) + 1 $$

然后对于使用魔力，我们可以直接用双指针去找最高可以在那一棵树开始即可。

代码：

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

const int maxn = 3e5 + 10;
int n,k,a[maxn],b[maxn],ch[maxn][2];
int stk[maxn],dp[maxn],top;
int maxx[maxn];
pair<int,int> p[maxn];
void build()
{
    for(int i = 1;i <= n;i++)
    {
        int pos = 0;
        while(top && a[stk[top]] <= a[i])pos = stk[top],top--;
        if(top)ch[stk[top]][1] = i;
        ch[i][0] = pos;stk[++top] = i;
    }
}

void turns(int u,int ls){dp[u] = max(dp[u],dp[ls] - (a[u] == a[ls]) + 1);}

void dfs(int u)
{
    if(ch[u][0])dfs(ch[u][0]),turns(u,ch[u][0]);
    if(ch[u][1])dfs(ch[u][1]),turns(u,ch[u][1]);
}

signed main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)cin >> a[i],p[i] = {a[i],i};
    for(int i = 1;i <= k;i++)cin >> b[i];
    build();dfs(stk[1]);sort(p + 1,p + n + 1);sort(b + 1,b + k + 1);
    int ans = dp[1];
    for(int i = 1;i <= n;i++)maxx[i] = max(maxx[i - 1],dp[p[i].second]);
    int j = 1;
    for(int i = 1;i <= n;i++)
    {
        while(p[i].first == p[i + 1].first)i++;
        while(b[j] < p[i + 1].first && j <= k)ans += maxx[i],j++;
    }
    while(j <= k)ans += maxx[n],j++;
    cout << ans;
    return 0;
}