牛客8409H - Equivalent Prefixes

• https://ac.nowcoder.com/acm/contest/8409/H
• ICPC2020 · 小米

题意

• 给出两个长为 $nn$ 的数组 $a_{i}a\_i$，$b_{i}b\_i$，求最大的前缀 $q(1\le q\le n)q(1\backslash leq\; q\; \backslash leq\; n)$ 满足其任意子区间的 ${\text{RMQ}}_a(l,r)={\text{RMQ}}_b(l,r)\backslash text\{RMQ\}\_a(l,r)=\backslash text\{RMQ\}\_b(l,r)$，其中 $l\le r\le ql\backslash leq\; r\; \backslash leq\; q$。
• ${\text{RMQ}}_w(l,r)\backslash text\{RMQ\}\_w(l,r)$ 指 $w_l,w_{l+1},\mathrm{}\dots ,w_r\mathrm{}w\_l,w\_\{l+1\},\backslash dots,w\_r$ 中最小值的下标。
• 保证 $a_{i}a\_i$ 中和 $b_{i}b\_i$ 中的数字两两不同。

思路

• 观察样例可得，对于一段合法的前缀，首先需要保证 $a_{i}a\_i$ 和 $b_{i}b\_i$ 中相邻元素的大小变化情况相同。
• 仅仅是上面的条件是不够的，来看一组数据：

7
5 1 6 2 4 3 9
5 1 6 3 4 2 9

• 如果仅依据上面的这一个条件，得出的答案是 $77$，实际的答案是 $55$。
• 考虑单调栈。
• 我们知道，一个单调上升的单调栈，插入一个数字，如果该数字会影响到区间的最小值，一定有弹栈的操作。
• 因此，维护两个单调上升的单调栈，对于某个 $ii$，如果 ${\text{stack}}_a\mathrm{.}\text{size}\mathrm{\ne }{\text{stack}}_b\mathrm{.}\text{size}\backslash text\{stack\}\_a.\backslash text\{size\}\; \backslash neq\; \backslash text\{stack\}\_b.\backslash text\{size\}$，那么 $\text{ans}=i-1\backslash text\{ans\}=i-1$。

代码

#include <cstdio>
#include <iostream>
#include <stack>
const int N		= 1e6+10;
using namespace std;

stack<int> stk1, stk2;
int ai[N],bi[N];
int n;

void Sol()
{
	while(!stk1.empty())stk1.pop();
	while(!stk2.empty())stk2.pop();
	
	for (int i=1; i<=n; i++)
	{
		while (!stk1.empty() && ai[stk1.top()]>=ai[i]) 
			stk1.pop();
		while (!stk2.empty() && bi[stk2.top()]>=bi[i]) 
			stk2.pop();
		
		stk1.push(i);
		stk2.push(i);
		
		if(i>=2 && (ai[i]>ai[i-1])!=(bi[i]>bi[i-1]))
		{
			printf("%d\n",i-1);
			return;
		}
		
		if(stk1.size()!=stk2.size())
		{
			printf("%d\n",i-1);
			return;
		}
	}
	printf("%d\n",n);
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		for (int i=1; i<=n; i++)
		{
			scanf("%d",&ai[i]);
		}
		for (int i=1; i<=n; i++)
		{
			scanf("%d",&bi[i]);
		}
		Sol();
	}
	return 0;
}