牛客网多校训练第四场C sequence

（牛客场场有笛卡尔树，场场都不会用笛卡尔树。。。自闭，补题心得）

题目链接：https://ac.nowcoder.com/acm/contest/884/C

题意：给出两个序列a,b,求max{min a[l,r]*sum b[l,r]}

一个比较显然的做法是通过线段树/ST表维护区间最值，不过nlogn的做法容易被卡常，(zkw线段树可过)不过赛时提高了时限到3s,基本上就很好写了

直接维护区间最小/大值下标，然后从最小值开始进行计算答案，在最小值的左边找到最小/最大的前缀和(找最大是为了处理min a[i]<0的情况)，最小值的右边也找到最小/最大值的前缀和，计算一次答案，然后以最小值为分界，划分为两部分继续计算即可

线段树查询效率logn,总复杂度O(nlogn),ST表预处理nlogn，总复杂度也是O(nlogn)且常数较大，赛后发现有神仙用了O(n)的做法，也学习了一下，没错，就是神奇的笛卡尔树

我们分析这个求解答案的过程，发现就是先找最小值，然后找次小...的顺序，我们对a数组构建笛卡尔树，那么这个求解答案的过程就是对树的dfs的过程，既然是对树的dfs，我们就可以用mn[rt],mx[rt]数组来记录以rt为根这颗子树中包含前缀和的最小前缀和，

然后在dfs的过程中，用子树不断更新即可，然后我们O(1)地计算每颗子树的答案即可，总体复杂度是O(n)的

笛卡尔树:

通过单调栈来构造，这个过程是O(n)的，每次元素x入栈，找到前一个比他小的元素p，那么它就是这颗笛卡尔树上元素p对应节点的右儿子，原先的右儿子q变成了当前插入元素x的左儿子，原先的右儿子q也就是最后一个出栈的元素，如果没有元素出栈，那就是作为一个叶子节点插入了笛卡尔树，插入位置是未入栈时栈顶元素的右儿子

笛卡尔树的性质：元素下标满足二叉搜索树的性质，元素值满足堆的性质

笛卡尔树根节点是单调栈栈底元素，也是整个序列的最小值，每颗子树的根节点都是一个范围内的极小值，树上两个元素的LCA可以用来解决RMQ问题

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N  = 3e6+;

int a[N];

ll b[N];

int son[N][],n;//0左儿子1右儿子

int sta[N];

ll mn[N],mx[N];//记录当前子树中最小、最大的前缀和

ll ans=-3e18;

void dfs(int rt,int l,int r)

{

    if(son[rt][])dfs(son[rt][],l,rt-);

    if(son[rt][])dfs(son[rt][],rt+,r);

    //左子树不包括l-1这个点，然而我们要将这个前缀和考虑进去，否则会少计算到b[l]，右子树不包括根节点，b[rt]也要考虑进去

    ll minl=min(mn[son[rt][]],b[l-]);

    ll maxl=max(mx[son[rt][]],b[l-]);

    ll minr=min(mn[son[rt][]],b[rt]);

    ll maxr=max(mx[son[rt][]],b[rt]);

    ans=max(ans,a[rt]*(maxr-minl));

    ans=max(ans,a[rt]*(minr-maxl));

    //这样写同时也把当前子树根考虑进去了

    mn[rt]=min(minl,minr);

    mx[rt]=max(maxl,maxr);

}

int main()

{

    int n;

    ios::sync_with_stdio(false);

    cin.tie();

    cout.tie();

    cin>>n;

    int top=;

    for(int i=;i<=n;i++)

    {

        cin>>a[i];

        while (top&&a[i]<a[sta[top]])son[i][]=sta[top--];

        if(top)son[sta[top]][]=i;

        sta[++top]=i;

    }

    for(int i=;i<=n;i++)

    {

        cin>>b[i];

        b[i]+=b[i-];

    }

    mn[]=3e18;mx[]=-3e18;

    dfs(sta[],,n);

    cout<<ans<<endl;

    return ;

}

巴特西

牛客网多校训练第四场C sequence

最新文章

热门文章