您的位置: 首页  >  IT文章  >  2019牛客暑期多校训练营（第一场）A题【单调栈】（补题）

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

分类: IT文章 • 2023-11-04 15:47:55

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

OUTPUT
For each test case, print an integer which denotes the result.
输入
2
1 2
2 1
3
2 1 3
3 1 2
5
3 1 5 2 4
5 2 4 3 1

输出

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

思路：让。
AC代码：
 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 struct str{
 5     int val;    
 6         int pos;
 7 
 8 };
 9 int main(){
10     int n;
11     while(~scanf("%d",&n)){
12         int a[n+10];
13         int b[n+10];
14         deque<str> q1,q2;
15         for(int i=1;i<=n;i++)
16             scanf("%d",&a[i]);
17         for(int i=1;i<=n;i++)
18             scanf("%d",&b[i]);
19         q1.push_front((str){-10000000,0});
20         q2.push_front((str){-10000000,0});
21         int arr1[n+10];
22         int arr2[n+10];
23         for(int i=1;i<=n;i++){
24             while(!q1.empty()&&q1.front().val>a[i])
25                 q1.pop_front();
26             arr1[i]=q1.front().pos;
27             q1.push_front((str){a[i],i});
28             while(!q2.empty()&&q2.front().val>b[i])
29                 q2.pop_front();
30             arr2[i]=q2.front().pos;
31             q2.push_front((str){b[i],i});
32         }
33         int ans=1;
34     
35         for(int i=1;i<=n;i++){
36             if(arr1[i]==arr2[i]){
37                 ans=i;
38             }else{
39                 break;
40             }
41         }
42         printf("%d
",ans);
43     }
44     
45     return 0;
46 }

相关推荐