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

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;
}
上一篇:Python中的Python字符串’Template’等效


下一篇:Proving Equivalences (强连通,缩点)