题解：P8051 [ZYOI Round1] Bird/鸟

sqrtqwq · 2025-07-23 18:50:06 · 题解

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

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

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

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

代码：

#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;
}