2019牛客暑期多校训练营 A 笛卡尔树 OR 单调栈

https://ac.nowcoder.com/acm/contest/881/A

Equivalent Prefixes

题意：给你两个数组a，b，大小为n，让你寻找一个数p (1<= p <= n) ，使之在 1~p 任意一个区间中a,b数组的最小值下标相同。

笛卡尔树：

概念

笛卡尔树的树根是这一子树中键值最小（或最大）的元素；且对于某个序列的笛卡尔树，其任一子树的中序遍历恰好是对应了原序列中的一段连续区间。

性质

我们会发现笛卡尔树同时满足二叉树搜索和堆的性质：

中序遍历即为原数组序列
父节点的键值均小于（或大于）其左右子节点的键值

我们可以将问题转化为 1~p内，a和b的笛卡尔树是否相同

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int b[N];
int l[2][N];//l[i] 表示 i 节点的左孩子的数组下标
int r[2][N];//r[i] 表示 i 节点的右孩子的数组下标
int rt[2];
stack<int> s;

int dfs(int u){
    if(l[0][u]!=l[1][u] || r[0][u]!=r[1][u])
        return 0;
    int ok = 1;
    if(l[0][u])
        ok &= dfs(l[0][u]);
    if(r[0][u])
        ok &= dfs(r[0][u]);
    return ok;
}

int gao(int x){
    for(int i = 1; i <= x; i++){
        l[0][i] = r[0][i] = 0;
        while(!s.empty() && a[i] < a[s.top()])
            l[0][i] = s.top() , s.pop();
        if(!s.empty()){//栈顶元素 < a[i] ，i为其右孩子 
            r[0][s.top()] = i;
        }
        s.push(i);
    }
    while(!s.empty()){
        rt[0] = s.top(),s.pop();
    }
    for(int i = 1; i <= x; i++){
        l[1][i] = r[1][i] = 0;
        while(!s.empty() && b[i] < b[s.top()])
            l[1][i] = s.top() , s.pop();
        if(!s.empty()){
            r[1][s.top()] = i;
        }
        s.push(i);
    }
    while(!s.empty()){
        rt[1] = s.top(),s.pop();
    }
    if(rt[0]!=rt[1])
        return 0;
    return dfs(rt[0]);
}

int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
        }
        int l=1,r=n,mid;
        while(l<=r){
            mid=(l+r)/2;
            if(gao(mid)) l = mid + 1;
            else r = mid - 1;
        }
        cout << r << "\n";
    }
    return 0;
}

单调栈：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int b[N];
int l[2][N];
int r[2][N];
// l[i] r[i] 表示以 i 为最小值的最大区间左右边界 区间长度：r[i] - l[i] -1
//在这个题里面只需要l[i]
stack<int> s;

void init(int *c,int k){
    l[k][0] = 0;
    for(int i = 1; i <= n; i++){
        while(!s.empty() && c[i] < c[s.top()]){
            r[k][s.top()] = i; s.pop();
        }
        if(!s.empty()){
            l[k][i] = s.top();
        }
        else l[k][i] = 0;
        s.push(i);
    }
    while(!s.empty()){
        r[k][s.top()] = n+1;
        s.pop();
    }
}

int gao(int x){
    for(int i = 1; i <= x; i++){
        if(l[0][i]!=l[1][i]){
            return 0;
        }
    }
    return 1;
}

int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
        }
        init(a,0);
        init(b,1);
        int l=1,r=n,mid;
        while(l<=r){
            mid=(l+r)/2;
            if(gao(mid)) l = mid + 1;
            else r = mid - 1;
        }
        cout << r << "\n";
    }
    return 0;
}