[ZJ d110][NOIP 2008 提高组]双栈排序

為了方便起見，稱原序列的第$i$個元素$S_{i}$
我們先來看看甚麼情況下$S_{i}$和$S_{j}$ ($i<j$)必須被分別放在兩個棧
首先，$S_{i}<S_{j}$是必須的，否則他們就會是獨立的
然後，所有$k<i$的$S_{k}$也不會影響

最後，當情況列舉完，我們會發現當$i<j<k$且$S_{k}<S_{i}<S_{j}$的時候，$S_{i}$和$S_{j}$必須被分別放在兩個棧，否則可以放在同一個

可以考慮當$S_{i}$和$S_{j}$不能放在同一個棧的時候，將$i$和$j$之間連邊
然後這個序列可二棧排序當且僅當整張圖是二分圖 (連通性不重要)
也就是，將每個點著黑白兩色，同色點不能相鄰

可以想到一個$O(N^{3})$建圖的方法 (枚舉$i$、$j$、$k$)
然後$O(N+M)$ ($M$是邊數) 決定每個點放在哪個棧
$O(N)$輸出解答

可是$O(N^{3})$建圖實在太耗時間了，我們必須想一個方法，$O(1)$判斷$i$和$j$之間要不要連邊，這樣就可以將複雜度降到$O(N^2)$
可以發現，我們只需要確定有沒有合法的$k$就好了
而$k$只要滿足$j<k$且$S_{k}<S_{i}$
可以發現，$k$越大，符合第一種條件的機率就越大
因此我們對於每個$i$，找出最大的$k$符合$S_{k}<S_{i}$就好了
這個預處理可以用單調隊列做到$O(N)$，不過很顯然在此題沒有意義

時間複雜度：$O(N^2)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
const int INF=2147483647;
int N,S[1000],RIGHT_LOWER[1000];
vector<int>ET[1000];
int COLOR[1000];
bool Color(const int u,const int color)
{
    if(COLOR[u]!=-1)return COLOR[u]==color;
    COLOR[u]=color;
    for(const int nxt:ET[u])if(!Color(nxt,color^1))return false;
    return true;
}
vector<char>ANS;
stack<int>A,B;
bool Solve()
{
    //i<j<k,S[k]<S[i]<S[j]
    for(int i=0;i<N;i++)
    {
        for(int j=N-1;;j--)if(S[j]<=S[i]){RIGHT_LOWER[i]=j;break;}
    }
    for(int i=0;i<N;i++)ET[i].clear();
    for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)if(S[i]<S[j])
    {
        if(RIGHT_LOWER[i]>j)ET[i].push_back(j),ET[j].push_back(i);
    }
    for(int i=0;i<N;i++)COLOR[i]=-1;
    ANS.clear();
    while(!A.empty())A.pop();
    while(!B.empty())B.pop();
    int cur=1;
    for(int i=0;i<N;i++)
    {
        if(COLOR[i]==-1)if(!Color(i,0))return false;
        if(COLOR[i]==0)A.push(S[i]),ANS.push_back('a');
        else if(COLOR[i]==1)
        {
            while(!B.empty()&&B.top()==cur)B.pop(),cur++,ANS.push_back('d');
            B.push(S[i]),ANS.push_back('c');
        }
        else assert(0);
        while(!A.empty()&&A.top()==cur)A.pop(),cur++,ANS.push_back('b');
    }
    while(!A.empty()||!B.empty())
    {
        if(!A.empty()&&A.top()==cur)A.pop(),cur++,ANS.push_back('b');
        if(!B.empty()&&B.top()==cur)B.pop(),cur++,ANS.push_back('d');
    }
    assert(cur==N+1);
    return true;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)scanf("%d",&S[i]);
        if(!Solve())puts("0");
        else
        {
            for(int i=0;i<(int)ANS.size();i++)
            {
                if(i)putchar(' ');
                putchar(ANS[i]);
            }
            puts("");
        }
    }
    return 0;
}