题目

双栈排序 $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;
}