2019牛客暑期多校训练营（第一场） A Equivalent Prefixes （单调队列）

题目

题意：找到最大的点$P$，使得两个数组 $a$ 和 $b$ 在区间$[1,P]$的任意子区间中的最小值下标相同

题解：对两个数组分别维护单调递增的单调队列。 每次插入后判断队列中的元素个数是否相同，不相同直接返回答案。 这样做保证了两个数组对应区间单调性相同，子区间个数也相同。

#include<bits/stdc++.h> using namespace std; const int maxn = 1e5+5; int a[maxn],b[maxn],n,q1[maxn],q2[maxn]; int solve(){ int f1 = 0, r1 = 0; int f2 = 0, r2 = 0; int ans; for(int i = 1; i <= n; i++){ while(f1 < r1 && a[i] <= a[q1[r1-1]]) r1--; q1[r1++] = i; while(f2 < r2 && b[i] <= b[q2[r2-1]]) r2--; q2[r2++] = i; if(r1-f1 != r2-f2) return i-1; ans = i; } return ans; } 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]); } printf("%d\n",solve()); } }