bzoj 3521: [Poi2014]Salad Bar

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3521

POI的题果然都有一些很精妙的$O(n)$做法
带log的比较简单，这里就不再赘述了
考虑一个区间怎么样是合法的
统计前缀和
假如一段区间$[l,r]$是合法的
那么必定满足$sum[r]$是最大的,$sum[l?1]$是最小的
于是固定一个$r$的时候，我们可以得到他的一个左端点$L$，满足这里所有的数$sum[r]$是最大的，这个用一个单调栈不难维护
于是去$[L,r]$中的最小值$l$，那么$[l,r]$就是$r$所能贡献的最大答案了
对于r端点递增，每一次寻找最小值，可以用并查集维护
就可以做到$O(n)$了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1000005;
int f[N];
int find_fa (int x) {
    return f[x]==x?f[x]:f[x]=find_fa(f[x]);}
int n;
char ss[N+1];
int sum[N];
int sta[N],top;
int sta1[N],top1;
int main()
{
    scanf("%d",&n);scanf("%s",ss+1);int ans=0;top=1;sta[top]=0;for (int u=1;u<=n;u++){
    f[u]=u;sum[u]=sum[u-1]+(ss[u]=='p'?1:-1);while (top>0&&sum[sta[top]]>sum[u])   {
    f[find_fa(sta[top])]=u;top--;}sta[++top]=u;while (top1>0&&sum[sta1[top1]]<=sum[u]) top1--;int L=sta1[top1];if (L!=0) L++;sta1[++top1]=u;int now=u-find_fa(L);ans=ans>now?ans:now;}printf("%d\n",ans);return 0;
}