題干：

鏈接：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)

for all 1≤l≤r≤m
where RMQ(w,l,r) denotes the index of the minimum element among 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≤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

輸入

復制

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是具有單調性的，換句話說，假設p=x成立，那么對任意p=1,2,3...x都成立。（因為他求的區間個數是絕對遞增的而且是完全包含之前的區間的）

那么運用數學歸納法的思維，先假設p=i成立，那么當p=i+1時，要考慮的區間就是左端點1~i，右端點i+1。先只考察一個數組的時候，很顯然能發現的一個問題就是，因為這個題目只關心最小值，所以區間的左端點從i到1變化的時候，如果變化到j了發現a[j] < a[i+1]，則左端點<=j那些區間肯定都不用看了（因為最小值與a[i+1]無關，也就是此時【左端點，i+1】的情況和【左端點，i】的情況相同，又因為假設了p=i成立，所以那些區間肯定成立）。換句話說，a[i+1]只承擔左端點為j+1~i的最小值。

回到這個題目，所以只需要比較對于每個p，兩個數組求出的j的值是否相同就可以了，如果不相同的話一定就GG。（找交叉部分的區間的某個點當左端點就一定不行）。再把問題抽象一下，就是要看每個點左側第一個比他小的點是否下標相同就可以了。

問題化簡到這里就很顯然了，思路就是單調棧。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<stack> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; const int INF = 0x3f3f3f3f; int la[MAX],lb[MAX],a[MAX],b[MAX],n; stack<int> sa,sb; int main() {while(~scanf("%d",&n)) {for(int i = 1; i<=n; i++) scanf("%d",a+i);for(int i = 1; i<=n; i++) scanf("%d",b+i);while(sa.size()) sa.pop();for(int i = 1; i<=n; i++) {while(sa.size() && a[i] < a[sa.top()]) sa.pop();if(sa.empty()) la[i] = 0;else la[i] = sa.top();sa.push(i);}while(sb.size()) sb.pop();for(int i = 1; i<=n; i++) {while(sb.size() && b[i] < b[sb.top()]) sb.pop();if(sb.empty()) lb[i] = 0;else lb[i] = sb.top();sb.push(i);}int ans = 0;for(int i = 1; i<=n; i++) {if(la[i] == lb[i]) ans = i;else break;}printf("%d\n",ans);}return 0 ; }

注意一個小細節：最后判斷的時候，不能這么寫，不然還得特判當沒有break的時候，ans=n。或者直接賦初值ans=n。

for(int i = 1; i<=n; i++) {if(la[i] != lb[i]) {ans = i-1;break;} }

?

總結

以上是生活随笔為你收集整理的【2019牛客暑期多校训练营（第一场） - A】Equivalent Prefixes（单调栈，tricks）的全部內容，希望文章能夠幫你解決所遇到的問題。

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