鏈接：https://ac.nowcoder.com/acm/contest/881/A
來源：牛客網

Equivalent Prefixes
時間限制：C/C++ 2秒，其他語言4秒
空間限制：C/C++ 524288K，其他語言1048576K
64bit IO Format: %lld
題目描述
Two arrays u and v each with m distinct elements are called equivalent if and only if
R
M
Q
(
u
,
l
,
r
)
=
R
M
Q
(
v
,
l
,
r
)
RMQ(u,l,r)=RMQ(v,l,r) for all
1
≤
l
≤
r
≤
m
1≤l≤r≤m
where
R
M
Q
(
w
,
l
,
r
)
RMQ(w,l,r) denotes the index of the minimum element among
w
l
,
w
l

• 1
  ,
  …
  ,
  w
  r
  wl,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
≤
n
p≤n where
{
a
1
,
a
2
,
…
,
a
p
}
{a1,a2,…,ap} and
{
b
1
,
b
2
,
…
,
b
p
}
{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
a
1
,
a
2
,
…
,
a
n
a1,a2,…,an.
The third line contains n integers
b
1
,
b
2
,
…
,
b
n
b1,b2,…,bn.

• 1
  ≤
  n
  ≤
  10
  5
  1≤n≤105
• 1
  ≤
  a
  i
  ,
  b
  i
  ≤
  n
  1≤ai,bi≤n
• {
  a
  1
  ,
  a
  2
  ,
  …
  ,
  a
  n
  }
  {a1,a2,…,an} are distinct.
• {
  b
  1
  ,
  b
  2
  ,
  …
  ,
  b
  n
  }
  {b1,b2,…,bn} are distinct.
• The sum of n does not exceed
  5
  ×
  10
  5
  5×105.
  輸出描述:
  For each test case, print an integer which denotes the result.
  示例1
  輸入
  復制
  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，大小為n，讓你尋找一個數p (1<= p <= n) ，使之在 1~p 任意一個區間中a,b數組的最小值下標相同。
思路：

容易知道p的取值具有單調性，首先我們用st表在對數組a，b進行預處理，方便后續的RMQ，因為數組中的數相互不同，那么我們就可以直接RMQ獲得區間最小值下標。

在二分p的過程中，我們這樣來判斷mid是否合法：

詢問1~mid 區間兩個數組中的最小值下標是否一致，如果不一致直接返回false，否則 以最小值下標minid為分界點遞歸處理1~minid，minid+1~mid。這個過程是O（n）的

所以總體時間復雜度是 O( n* log n )

細節見代碼：

#include<iostream> using namespace std; const int maxn=2e5+10; int n; int a[maxn],b[maxn]; int sa[maxn][20],sb[maxn][20],mn[maxn]; void init() {mn[0]=-1;for (int i=1;i<=n;i++){mn[i]=((i & (i-1))==0) ? mn[i-1]+1 : mn[i-1];sa[i][0]=a[i];sb[i][0]=b[i];}for (int j=1;j<=mn[n];j++)for (int i=1;i+(1<<j)-1<=n;i++){sa[i][j]=min(sa[i][j-1],sa[i+(1<<(j-1))][j-1]);sb[i][j]=min(sb[i][j-1],sb[i+(1<<(j-1))][j-1]);} } int ida[maxn]; int idb[maxn]; int rqa(int L,int R) {int k=mn[R-L+1]; // cout<<"a "<<min(sa[L][k],sa[R-(1<<k)+1][k])<<endl;return ida[min(sa[L][k],sa[R-(1<<k)+1][k])]; } int rqb(int L,int R) {int k=mn[R-L+1]; // cout<<"b "<<min(sb[L][k],sb[R-(1<<k)+1][k])<<endl;return idb[min(sb[L][k],sb[R-(1<<k)+1][k])]; } bool pan(int l,int r) {if(l>=r){return 1;}int w=rqb(l,r);int q=rqa(l,r);if(w!=q){return 0;}else{return pan(l,w-1)&&(pan(q+1,r));} } bool check(int mid) { // bool res=1;return pan(1,mid); } int main(){while(~scanf("%d",&n)){for(int i=1;i<=n;i++){scanf("%d",&a[i]);ida[a[i]]=i;}for(int i=1;i<=n;i++){scanf("%d",&b[i]);idb[b[i]]=i;;}init();int l=1;int r=n;int mid;int ans=1;while(l<=r){mid=(l+r)>>1;if(check(mid)){l=mid+1;ans=mid;}else{r=mid-1;}}printf("%d\n",ans);} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11209227.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的2019牛客暑期多校训练营（第一场） AEquivalent Prefixes ( st 表 + 二分+分治)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。