2019牛客暑期多校训练营（第一场）A题【单调栈】（补题）

链接：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.

input

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.

OUTPUT

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

输出

题意：给出两个序列A和B，让你找出最大的一个p，使得在区间[1,p]内，任意的l，r∈[1,n],RMQ(l,r,A)要等于RMQ(l,r,B)。RMQ(l,r,A)返回的是[l,r]内最小值对应的下标。

思路：让ai和bi同时进入单调队列，单调队列保存元素的值和下标，如果进队/出队的时候，ai所在的单调队列和bi所在的单调队列的下标值是一样的，那么就是OK的，直到找到状态不一样的位置，那么答案为它的前一个。渐进时间复杂度O(n)。
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 struct str{

     int val;

         int pos;

 };

 int main(){

     int n;

     while(~scanf("%d",&n)){

         int a[n+];

         int b[n+];

         deque<str> q1,q2;

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

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

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

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

         q1.push_front((str){-,});

         q2.push_front((str){-,});

         int arr1[n+];

         int arr2[n+];

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

             while(!q1.empty()&&q1.front().val>a[i])

                 q1.pop_front();

             arr1[i]=q1.front().pos;

             q1.push_front((str){a[i],i});

             while(!q2.empty()&&q2.front().val>b[i])

                 q2.pop_front();

             arr2[i]=q2.front().pos;

             q2.push_front((str){b[i],i});

         }

         int ans=;

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

             if(arr1[i]==arr2[i]){

                 ans=i;

             }else{

                 break;

             }

         }

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

     }

     return ;

 }