vijos1605 很迷的一道题 大概就是要用两个栈，通过出栈入栈来排序 这道题出题人良心啊帮我们离散好了
首先考虑单栈排序
很显然的是 例如 2 3 1这种情况，我们就不能通过一个栈来排序，因为1要比2先出栈，然而1如果要出栈，3就一定会比2先出栈，这种规律我们可以认为是： 当a[i]>a[j]且i~j中有a[k]>a[i]，则i,j两个数字矛盾
如果求出这个矛盾关系，我们只要模拟一下就可以了
然而显然是n^3的，对于N=1000直接gg
那么怎么办呢
我们可以不求i,j矛盾，而是认为i,k矛盾，那么我们就不需要去枚举j，因为我们只需要找到是否有a[j]小于a[i]，一个后缀最小值就可以了
构建完矛盾关系，我们就xjb染色一下，如果矛盾的数量比2大，则无解。。迷之。。二分图？
然后就可以了，看别人代码神tm短。。算了反正我代码长是一种常态
CODE：
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<string> #include<map> #include<cstring> #include<vector> #define inf 1e9 #define ll long long #define For(i,j,k) for(int i=j;i<=k;i++) #define Dow(i,j,k) for(int i=k;i>=j;i--) using namespace std; int poi[1000001],nxt[1000001],f[10001],mi[10001],a[10001],sta1[10001],sta2[10001],top1,top2,n,clr[10001],cnt; void dfs(int co,int x) { if(!clr[x]) clr[x]=co; else if(clr[x]==co) return;else {puts("0");exit(0);} for(int i=f[x];i;i=nxt[i]) dfs(3-co,poi[i]); } inline void add(int x,int y) { poi[++cnt]=y;nxt[cnt]=f[x];f[x]=cnt; poi[++cnt]=x;nxt[cnt]=f[y];f[y]=cnt; } int main() { scanf("%d",&n); For(i,1,n) scanf("%d",&a[i]); mi[n+1]=inf; Dow(i,1,n) mi[i]=min(mi[i+1],a[i]); For(i,1,n) For(j,i+1,n) if(a[i]<a[j]&&a[i]>mi[j+1]) add(i,j); For(i,1,n) if(!clr[i]) dfs(1,i); int now=1; For(i,1,n) { while(1) { bool flag=0; if(sta1[top1]==now){now++;top1--;printf("b ");flag=1;} if(sta2[top2]==now){now++;top2--;printf("d ");flag=1;} if(!flag) break; } if(clr[i]==1) sta1[++top1]=a[i],printf("a "); else sta2[++top2]=a[i],printf("c "); } while(1) { bool flag=0; if(sta1[top1]==now){now++;top1--;printf("b ");flag=1;} else if(sta2[top2]==now){now++;top2--;printf("d ");flag=1;} if(!flag) break; } }