[POI 21 Stage 1] Salad bar

作法：

首先當然是先求出前綴和，就是令 p = 1 , j = - 1 之後求陣列的前綴和，在後面用 a[ i ] 表示轉換後的陣列 ( 只有 1 和 -1 ) ， sum[ i ] = a[ 1 ] + ... + a[ i ]。
如果答案的區間是 i + 1 ~ j ( 等一下的表示會比較簡潔 )，那麼題目的條件就可以等價成 a[ i + 1 ] + ... + a[ k ] >= 0 ，對於每一個 k 屬於 [ i + 1 , j ] ，並且 a[ k ] + ... + a[ j ] >= 0 ，一樣對於每一個 k 屬於 [ i + 1 , j ]。這可以寫成  sum[ k ] - sum[ i ] >= 0 且 sum[ j ] - sum[ k ] >= 0 ，對於每一個 k 屬於 [ i , j ] 。也就是 sum[ i ] <= sum[ k ] <= sum[ j ] ，對於每一個 k 屬於 [ i , j ] 。這樣就可以把這個條件圖像化了，考慮把 ( i , sum[ i ] ) 畫在座標平面上，就會變成一些折線，並且一個區間滿足條件若且唯若區間中間的折線都不跨出左端點高度和右端點高度形成的區間。

所以對於每一個左端點 i ，記他右邊的第一個 sum 值小於 sum[ i ] 的位置是 dn[ i ] ，那麼以 i 為左端點的答案區間右端點不能超過 dn[ i ]。再來看看右邊第一個 sum 值大於等於 sum[ i ] 的點 ( 之後叫他 up[ i ] )，記 x1 = up[ i ]，如果 x1 > dn[ i ] ，那 i 為左端點的情況就作完了( 因為這也代表 i 的下一步是往下走的，不可能會形成答案區間 )。如果 x1 <= dn[ i ] ，代表 i ~ x1 是一個可行的解的區間。繼續考慮 up[ x1 ]  ( 記為 x2 ) ，如果 x2 還是 <= dn[ i ] 的話， i ~ x2 也是一個可行的解的區間，所以如果可以一直跳下去並且不超過 dn[ i ] 的話，那麼跳到越遠是越好的。也就是如果令 x_r = up[ x_(r-1) ] ，對於所有 r >= 2 ( 若一個數右邊沒有大於等於他的數，那 up 就設成 n + 1 )，並且 t 是滿足 x_t < dn[ i ] 且 x_( t + 1 ) >= dn[ i ] 的數，那麼以 i 為左端點的區間取 x_t 為右端點是最好的。

但如果對每個 i 都作一次會讓解退化成 O( n ) 的，這只要注意到，如果 [ a , c ] 和 [ b , d ] 都是可行的區間，並且滿足 a <= b <= c <= d ，那麼因為他是可行區間，所以有 sum[ a ] <= sum[ b ] <= sum[ c ] <= sum[ d ] ，這樣就可以推出 [ a , d ] 也是可行的區間。所以當我們找到一個 i 的最佳右端點 x_t 時，下一步的左端點就可以從 x_t 開始考慮了 ( 由上面的性質知道左端點如果落在 i 和 x_t 之間不會有更好的解 ) ，這樣就讓解變成 O( n ) 了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10 ;
 
int a[maxn] ;
char c[maxn] ;
int dn[maxn],up[maxn] ;
stack<int> st1,st2 ;
main()
{
    int n ; scanf("%d%s",&n,c+1) ;
    for(int i=1;i<=n;i++) a[i]=a[i-1]+ (c[i]=='p'?1:-1) ;
    for(int i=n;i>=0;i--)
    {
        dn[i]=up[i]=n+1 ;
        while(!st1.empty() && a[st1.top()]<a[i]) st1.pop() ;
        if(!st1.empty()) up[i]=st1.top() ;
        while(!st2.empty() && a[st2.top()]>=a[i]) st2.pop() ;
        if(!st2.empty()) dn[i]=st2.top() ;
        st1.push(i) ;
        st2.push(i) ;
    }
 
    int ans=0 ;
    for(int i=0;i<=n;)
    {
        int j=i ;
        while(up[j]!=n+1 && up[j]<=dn[i]) j=up[j] ;
        ans=max(ans,j-i) ;
        i=j+1 ;
    }
    printf("%d\n",ans) ;
}