Equivalent Prefixes 单调栈（笛卡尔树）

题意：

给出两个数组u,v，每个数组都有n个不同的元素，RMQ（u,l,r）表示u数组中[l,r]区间里面的最小值标号是多少，求一个最大的m，使得两个数组中[1,m]任一区间的最小值标号都相同

分析

想到最小值标号并且是在一维数组中，就要很自然地想到单调栈，同时笛卡尔树和单调栈密不可分，所以衍生了两种解法。

解法1：单调栈

从左到右扫，如果左边界相同，则继续往左扫，直到找到最大值。

证明reference:https://www.cnblogs.com/ZGQblogs/p/11210004.html

（引用自上博客）单调栈:

记录每个值的左边第一个比当前值小的位置。

从左到右遍历一遍，记录下第一个单调栈结果不同的地方，该位置前一个位置就是答案。

证明：

如果你确认了位置i是正确的，并且单调栈记录的位置是pos，那么（pos,i）,(pos+1,i）... (i,i)都是符合条件的。

如果pos左侧的值都比pos处的值要大，那么显而易见，（1,i）,（2,i）,...,(pos-1,i)也是符合题意的。

如果pos左侧的值有比pos处的值小的，那么从右边数，第一个比pos小的值的位置pos2，对于两个数组，也一定相等，(因为之前已经检测过pos了，不然也不会走到i)

那么（pos2+1,i),(pos2+2,i)...(pos-1,i)也是符合题意的。

再从pos2开始考虑，用类似递归的思想，很容易明白，（1,i）,（2,i）,...,(pos-1,i)都是符合题意的。

这是右端点是i的情况，但是因为i从左向右遍历，所以之前的所有区间其实都已经检测过了。

再考虑不相等的情况：

如果在位置i，第一个数组从右向左的第一个位置为pos1，第二个是pos2，且pos1<pos2

那么对于第一个数组，（pos2,i)的最小值位置是i，对于第一个数组，（pos2,i)的最小值位置是pos2,显然不同。

解法2笛卡尔树：

由笛卡尔树定义我们可以知道，两个数组的区间最小值标号相同，其实就是笛卡尔树的结构相同，所以我们只要从1开始构造笛卡尔树，看最大构造到几笛卡尔树结构仍相同即可。而笛卡尔树的构造只在根节点或右节点构造，所以只要维护右子树即可。

#include<bits/stdc++.h>

#define F first

#define S second

#define pii pair<int,int>

#define pb push_back

#define mkp make_pair

#define all(zzz) (zzz).being(),(zzz).end()

#define pii pair<long long ,int>

typedef long long ll;

typedef long long LL;

using namespace std;

const int maxn=1e6+5;

int a[maxn],b[maxn];

int main(){

    int n;

    while(scanf("%d",&n)==1){

        for(int i=1;i<=n;i++)scanf("%d",&a[i]);

        for(int i=1;i<=n;i++)scanf("%d",&b[i]);

        stack<int>s1,s2;

        int i;

        for( i=1;i<=n;i++){

        while(!s1.empty()&&s1.top()>a[i])s1.pop();

        while(!s2.empty()&&s2.top()>b[i])s2.pop();

        s1.push(a[i]);

        s2.push(b[i]);

        if(s1.size()!=s2.size()){

            printf("%d\n",i-1);

            break;

        }

        }

        if(i==n+1)printf("%d\n",n);

    }

    return 0;

}

巴特西

牛客多校第一场 A Equivalent Prefixes 单调栈（笛卡尔树）

Equivalent Prefixes 单调栈（笛卡尔树）

题意：

分析

最新文章

热门文章