[ZYOI Round1] Bird/鸟 题解

· · 题解

神说，笛卡尔树秒了

如果不知道笛卡尔树的，可以去 OIwiki 里了解一下。接下来的讲解将依照笛卡尔树展开。

这是一种理解起来很方便，虽然不怎么常用的构造树，复杂度是 O(n)。

解题思路

OK，想必你已经大致了解了笛卡尔树是什么东西。

由题可得，设 sum[i] 为第i棵树能飞行的次数，那么 sum[i]=\max (sum[x]+1,sum[y]+1)。xy 即通过树 i 可以飞到的树。

我们观察题目不难发现，对于任意一棵树，想要飞的最多，下一步应该飞到这棵树左侧或右侧可到达的最高的树，因为左侧或右侧其它的树都可以通过这棵树飞到。

因此，我们可以构建一个大根的笛卡尔树。对于每一个节点，它的左儿子和右儿子即它左边和右边最大的那个节点。

接着我们依据公式 sum[i]=\max\ (sum[ls[i]]+1,sum[rs[i]]+1)，搜索得出每个节点可以飞行的次数。

最后，依据 b 数组，将 \max(sum[i\ (a[i]<b[j])\ ]) 加起来即可得出答案。

特别地，对于左右儿子节点与本节点相同的情况，根据题目与解法推理可得，只需要不记录相同的儿子节点即可(就是 sum[i] 不加一)。

时间复杂度的大头反而是排序，其余都是 O(n) 级别的。

O(n+nlogn) 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=3e5+5;
int n,k,ans;
int b[N],cot[N];
int rs[N],ls[N],sta[N],top,root;
struct str{
    int num,sum;
}a[N];

bool cmp(int x,int y){ return x>y; }
bool cmp2(str x,str y){ return x.sum>y.sum; }

int solve(int p)
{
    if(p==0)
        return 0;
    if(a[ls[p]].num==a[p].num)//左右儿子节点相同的情况 
        a[p].sum=max(a[p].sum,solve(ls[p]));
    else
        a[p].sum=max(a[p].sum,solve(ls[p])+1); 
    if(a[rs[p]].num==a[p].num)
        a[p].sum=max(a[p].sum,solve(rs[p]));
    else
        a[p].sum=max(a[p].sum,solve(rs[p])+1); 

    return a[p].sum;
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].num;      
        if(a[i].num>a[root].num)
            root=i;
    }
    for(int i=1;i<=k;i++)
        cin>>b[i];
    sort(b+1,b+1+n,cmp);
    //构建笛卡尔树 
    for(int i=1;i<=n;i++)
    {
        int p=top;
        while(a[i].num>a[sta[p]].num && p>0) p--;
        if(p>0) rs[sta[p]]=i;
        if(p<top) ls[i]=sta[p+1];
        sta[++p]=i;
        top=p;
    }
    //搜索求sum 
    solve(root);
    ans+=a[1].sum-1;//记得要减 1 
    sort(a+1,a+1+n,cmp2);
    top=1;
    for(int i=1;i<=n;i++)
    {
        while(b[top]>=a[i].num && top<=k)
        {
            ans+=a[i].sum-1;
            top++;
        }
    }
    cout<<ans;
    return 0;
}

求过。

想过审好难啊QWQ。