题目
双栈排序 \(O(n\log n)\) 版，\(O(n^2)\) 可过弱化版P1155。
分析
经过长时间的手玩数据，可以发现某些点不可能在同一个栈中，考虑总结一个规律。
对于下标 \(i,j(1\le i<j\le n)\)，若 \(a_i>a_j\)，由于栈是后进先出，\(i,j\) 之间没有任何限制；若 \(a_i<a_j\)，则必然要在 \(j\) 进入之前弹出 \(i\)，如果此时 \(j\) 后面有 \(a_k<a_i<a_j(i<j<k)\)，\(i\) 和 \(j\) 的进出栈顺序发生了矛盾，那么 \(i\) 和 \(j\) 一定不能放在一个栈中。
形式化地，对于 \(i<j<k\)，若 \(a_k<a_i<a_j\)，则 \(i\) 和 \(j\) 在不同的栈内。
这一限制可以通过二分图体现出来，结合染色法判定，给未确定的点赋予较小的栈号即可在 \(O(n^2+n+m)\) 时间内得出答案。
很明显无法通过，于是考虑优化。
优化建图
倒序枚举每个 \(j\)，维护后缀最小值 \(mn\)，值域在 \([mn+1,j-1]\) 之间且还没有枚举到的点与 \(j\) 连边。
区间连边可以使用线段树优化建图，分为入树和出树彼此连边即可。
重点考虑如何只连未枚举到的点。每枚举到一个点，就把线段树上连接对应叶子节点的边删去。实现上，由于之前连的边使用了旧节点，所以应当把根到该叶子节点上的所有点更换成新的点。
关于最终的图上的结点个数，可以简单算出应为 \(6.8\times10^6\) 左右，可能会稍卡空间，应当避免使用邻接表存图，链式前向星消耗更少。
建图上可以如图示建法，可以方便判断叶节点且减少点数。
DFS 的细节
与一般的染色法判定不同，对于线段树上的辅助点，是不能有一个具体的颜色的，因为可能有很多路径需要经过它。
最初的想法是记录当前访问的点 \(u\)、上一个经过的叶子节点 \(last\)，是否访问的数组 \(vis\)。对于下一步要走的点 \(v\)，如果是叶子节点，就用 \(last\) 和 \(v\) 比较。反之，由于不知道 \(v\) 之后会走到哪里，所以不管有没有访问过，都继续搜索 \(v\)。
很明显，时间直接爆炸，考虑对非叶节点 \(v\) 做出限制。
可以发现，如果搜完了点 \(v\)，那么对于当前的 \(last\)，经过点 \(v\) 可以访问的所有叶节点的颜色都与 \(last\) 不同，那么相当于只有颜色与 \(last\) 相同的可以满足二分图，不同的一定不行。可以把这个颜色记录在 \(v\) 上。就可以保证每个点只经过一次。
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N(1e5+10),M(6e6+8e5+10);
int n,a[N],tot,h[M],ne[M<<1],e[M<<1],idx;
bitset<M>vis,co,fg;
struct node{
int l,r,ii,oo;
}tr[N<<2];
inline void add(int u,int v){
ne[++idx]=h[u],h[u]=idx,e[idx]=v;
}
inline void pushup(int u){
add(tr[u].ii,tr[u<<1].ii),add(tr[u].ii,tr[u<<1|1].ii);
add(tr[u<<1].oo,tr[u].oo),add(tr[u<<1|1].oo,tr[u].oo);
}
inline void build(int u,int l,int r){
tr[u]=/**/{l,r};
if(l==r){
tr[u].ii=tr[u].oo=l;
return ;
}
tr[u].ii=++tot;tr[u].oo=++tot;
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
inline void mdf(int u,int l,int r,int x){
if(l<=tr[u].l&&tr[u].r<=r){
if(tr[u].l!=tr[u].r||!fg[tr[u].l])
add(x,tr[u].ii),add(tr[u].oo,x);
return ;
}
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) mdf(u<<1,l,r,x);
if(r>mid) mdf(u<<1|1,l,r,x);
}
inline void upd(int u,int x){
if(tr[u].l==tr[u].r) return ;
int mid=tr[u].l+tr[u].r>>1;
tr[u].ii=++tot;tr[u].oo=++tot;
upd(x<=mid?u<<1:u<<1|1,x);
if(tr[u<<1].l!=tr[u<<1].r||!fg[tr[u<<1].l])
add(tr[u].ii,tr[u<<1].ii),add(tr[u<<1].oo,tr[u].oo);
if(tr[u<<1|1].l!=tr[u<<1|1].r||!fg[tr[u<<1|1].l])
add(tr[u].ii,tr[u<<1|1].ii),add(tr[u<<1|1].oo,tr[u].oo);
}
inline void dfs(int u,int la){
vis[u]=1;
if(u>n) co[u]=co[la];
for(int i=h[u],v;i;i=ne[i]){
v=e[i];
if(v<=n){
if(!vis[v]){
co[v]=co[la]^1;
dfs(v,v);
}
else if(la!=v&&co[v]==co[la]){
puts("NIE");
exit(0);
}
}
else{
if(!vis[v]){
co[v]=co[la];
dfs(v,la);
}
else if(fg[v]&&co[u]!=co[v]){
puts("NIE");
exit(0);
}
}
if(u>n) fg[u]=fg[u]|fg[v];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
tot=n;
build(1,1,n);
for(int i=n,mn=2e9;i>=1;--i){
if(a[i]<mn) mn=a[i];
else if(mn<a[i]-1) mdf(1,mn+1,a[i]-1,a[i]);
fg[a[i]]=1;
upd(1,a[i]);
}
for(int i=1;i<=n;++i)
if(!vis[a[i]]) dfs(a[i],a[i]);
puts("TAK");
for(int i=1;i<=n;++i) printf("%d ",co[a[i]]+1);
return 0;
}