「LOJ 2430」「POI2014」沙拉餐厅 Salad Baralad Bar

LOJ #2430

题意

一排$n$个水果$a_1..a_n$，分别是苹果$(j)$和橘子$(p)$，求最长的区间满足从左向右和从右向左取水果，任意时刻都有橘子数$\ge$苹果数，输出最长的区间长度

$n\le 10^6$

---

分析

记$d_i=\sum_{x=1}^i[a_x=p]-\sum_{x=1}^i[a_x=j]$

一个区间$[l,r]$满足条件当且仅当$\forall l\le i\le r，d_l\le d_i\le d_r$

可以用单调栈处理出最近的$l$满足$d_l>d_i$，于是以$i$为右端点的区间，最小的合法左端点是$[l+1,i]$中的最小值（如果存在）。

这个区间最小值位置可以在单调栈里顺便维护一下

复杂度 $\mathcal O(n)$

---

代码

#include<cstdio>
#include<algorithm>
const int N = 1000005;
int n, top, ans, stk[N], a[N], f[N];
char s[N];
int main() {
	scanf("%d%s", &n, s+1);
	for(int i=1; i<=n; ++i){
		a[i]=a[i-1]+(s[i]=='j'?-1:1);
		while(top && stk[top]<=a[i]) (a[f[top-1]]>a[f[top]]?f[top-1]=f[top]:0), --top;
		if(a[f[top]]<=a[i]) ans=std::max(ans, i-f[top]);
		++top, stk[top]=a[i], f[top]=i;
	}
	return printf("%d", ans), 0;
}