「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;
}