2019牛客暑期多校训练营（第一场）A Equivalent Prefixes（单调栈/二分+分治）

链接：https://ac.nowcoder.com/acm/contest/881/A
来源：牛客网

Two arrays u and v each with m distinct elements are called equivalent if and only if RMQ(u,l,r)=RMQ(v,l,r)RMQ(u,l,r)=RMQ(v,l,r) for all 1≤l≤r≤m1≤l≤r≤m
where RMQ(w,l,r)RMQ(w,l,r) denotes the index of the minimum element among wl,wl+1,…,wrwl,wl+1,…,wr.
Since the array contains distinct elements, the definition of minimum is unambiguous.

Bobo has two arrays a and b each with n distinct elements. Find the maximum number p≤np≤n where {a1,a2,…,ap}{a1,a2,…,ap} and {b1,b2,…,bp}{b1,b2,…,bp} are equivalent.

输入描述:

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers a1,a2,…,ana1,a2,…,an.
The third line contains n integers b1,b2,…,bnb1,b2,…,bn.

* 1≤n≤1051≤n≤105
* 1≤ai,bi≤n1≤ai,bi≤n
* {a1,a2,…,an}{a1,a2,…,an} are distinct.
* {b1,b2,…,bn}{b1,b2,…,bn} are distinct.
* The sum of n does not exceed 5×1055×105.

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

输出

复制

1

3

4

题意：
两个长度为n的数组，求最大的m，使得1到m之内的所有区间的最小值位置相同。
思路：
单调栈:
记录每个值的左边第一个比当前值小的位置。
从左到右遍历一遍，记录下第一个单调栈结果不同的地方，该位置前一个位置就是答案。
证明：
如果你确认了位置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,显然不同。

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#define fuck(x) cerr<<#x<<" = "<<x<<endl;

#define debug(a, x) cerr<<#a<<"["<<x<<"] = "<<a[x]<<endl;

#define ls (t<<1)

#define rs ((t<<1)|1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = ;

const int maxm = ;

const int inf = 0x3f3f3f3f;

const ll Inf = ;

const int mod = ;

const double eps = 1e-;

const double pi = acos(-);

int num1[maxn],num2[maxn];

int ans1[maxn],ans2[maxn];

struct node{

    int num,id;

};

stack<node>st;

int main() {

//    ios::sync_with_stdio(false);

//    freopen("in.txt", "r", stdin);

    int n;

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

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

            scanf("%d",&num1[i]);

        }

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

            scanf("%d",&num2[i]);

        }

        num1[]=num2[]=-;

        int ans=n;

        for(int i=n;i>=;i--){

            while (!st.empty()&&st.top().num>num1[i]){

                ans1[st.top().id]=i;

                st.pop();

            }st.push(node{num1[i],i});

        }for(int i=n;i>=;i--){

            while (!st.empty()&&st.top().num>num2[i]){

                ans2[st.top().id]=i;

                st.pop();

            }st.push(node{num2[i],i});

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

            if(ans1[i]!=ans2[i]){

                ans=i-;

                break;

            }

        }printf("%d\n",ans);

    }

    return ;

}

二分+分治
如果位置p符合题意，那么pos<p也一定满足题意。
那么现在在check区间l,r是否满足题意。
如果区间(l,r)两个数组最小值位置都是pos，那么对于区间(L,R) l<=L<pos,r>=R>pos，最小值位置就是pos.
所以只需要考虑L，R都在pos同一边即可。
于是就是pos为分界线进行分治。
如果区间(l,r)两个数组最小值位置不同，直接返回false

#include <set>

#include <map>

#include <cmath>

#include <cstdio>

#include <string>

#include <vector>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

typedef pair<int, int> pii;

typedef unsigned long long uLL;

#define ls rt<<1

#define rs rt<<1|1

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define bug printf("*********\n")

#define FIN freopen("input.txt","r",stdin);

#define FON freopen("output.txt","w+",stdout);

#define IO ios::sync_with_stdio(false),cin.tie(0)

#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"

#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"

#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n"

const int maxn = + ;

const int INF = 0x3f3f3f3f;

int a[maxn], b[maxn];

int pos1[maxn], pos2[maxn];

int st1[maxn][];

int n;

void rmq_init1() {

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

        st1[i][] = a[i];

    }

    int l = ;

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

        for (int j = ; j + l /  <= n; j++) {

            st1[j][i] = min(st1[j][i - ], st1[j + l / ][i - ]);

        }

        l <<= ;

    }

}

int ask_min1(int i, int j) {

    int k = int(log(j - i + 1.0) / log(2.0));

    return min(st1[i][k], st1[j - ( << k) + ][k]);

}

int st2[maxn][];

void rmq_init2() {

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

        st2[i][] = b[i];

    }

    int l = ;

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

        for (int j = ; j + l /  <= n; j++) {

            st2[j][i] = min(st2[j][i - ], st2[j + l / ][i - ]);

        }

        l <<= ;

    }

}

int ask_min2(int i, int j) {

    int k = int(log(j - i + 1.0) / log(2.0));

    return min(st2[i][k], st2[j - ( << k) + ][k]);

}

bool check(int l,int r){

//    cout<<l<<" "<<r<<endl;

    if(l>=r) return true;

    int min1=ask_min1(l,r);

    int min2=ask_min2(l,r);

    int p1=pos1[min1];

    int p2=pos2[min2];

    if(p1==p2) {

        return check(l,p1-)&&check(p1+,r);

    }else{

        return false;

    }

}

int main() {

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

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

            scanf("%d", &a[i]);

            pos1[a[i]] = i;

        }

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

            scanf("%d", &b[i]);

            pos2[b[i]] = i;

        }

        rmq_init1();

        rmq_init2();

        int l=,r=n;

        int ans=;

        while(l<=r){

            int mid=(l+r)>>;

            if(check(,mid)){

                ans=mid;

                l=mid+;

            }else{

                r=mid-;

            }

        }

        printf("%d\n",ans);

    }

    return ;

}