Equivalent Prefixes【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.

输入描述:

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.

---

  我们可以去找每个点的左边的比它小的数的所在的位置，然后如果两点的左边比它小的数的位置不同，那么肯定这一位就不能取了。

#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef long long ll; const int maxN = 1e5 + 7; int N, a[maxN], b[maxN], l1[maxN], r1[maxN], l2[maxN], r2[maxN]; int main() { while(scanf("%d", &N) != EOF) { for(int i=0; i<=N + 1; i++) l1[i] = r1[i] = l2[i] = r2[i] = 0; for(int i=1; i<=N; i++) { scanf("%d", &a[i]); l1[i] = r1[i] = i; while(l1[i] > 0 && a[l1[i] - 1] >= a[i]) { l1[i] = l1[l1[i] - 1]; } } for(int i=1; i<=N; i++) { scanf("%d", &b[i]); l2[i] = r2[i] = i; while(l2[i] > 0 && b[l2[i] - 1] >= b[i]) { l2[i] = l2[l2[i] - 1]; } } int ans = 1; for(int i=2; i<=N; i++) { if(l1[i] != l2[i]) break; else ans = i; } printf("%d\n", ans); } return 0; }