模擬賽考了這題的加強(qiáng)版，我被肘飛了。模擬賽那題除了要判定是否合法之外，還要求構(gòu)造。感覺還是有跡可循的啊。

這題一個很重要的 Trick 就是 LIS 的分層，我們設(shè) \(f_i\) 表示以 \(p_i\) 結(jié)尾的 LIS 的長度。然后按照 \(f_i\) 進(jìn)行分組，值相同的在一組。可以發(fā)現(xiàn) \(f_i\) 相同的元素內(nèi)部不會形成 LIS，它們的結(jié)構(gòu)形如若干逆序?qū)Γ绻琼樞驅(qū)Φ脑挘蜁幸粋€ \(f\) 值更新另外一個導(dǎo)致它們的 \(f\) 值不同。

本質(zhì)是 Dilworth 定理，紫色的為最長鏈。淡藍(lán)色的若干反鏈，同一條淡藍(lán)色線上的 \(f\) 值相同。

令 LIS 長度為 \(2k/2k+1\)。

這個時候我們就可以輕松解決 LIS 為偶數(shù)的情況了，因為這樣子的藍(lán)線個數(shù)也為偶數(shù)，隨便選 \(k\) 組放在一起，另外 \(k\) 組放在一起。由于組內(nèi)不會產(chǎn)生貢獻(xiàn)，所有兩個部分的 LIS 都是 \(k\)。

對于 LIS 為 \(2k+1\) 的情況有點(diǎn)難做，考慮讓兩組的長度都是 \(k+1\)。可是我們只能劃分出 \(k\) 組合上 \(k+1\) 的情況。于是考慮“借”一個元素來完成這個構(gòu)造，如果如圖深藍(lán)色部分的選擇，我們選擇 \(k\) 條淺藍(lán)色的鏈的全部元素，然后借用另一條淺藍(lán)色線上的一個元素就行了，這樣子這一個子序列的 LIS 為 \(k+1\)，另一個子序列由于包含了 \(k+1\) 組，所以 LIS 也為 \(k+1\)。

選擇的這個元素必須滿足其所在組的大小 \(>1\)（否則我們?nèi)⊥赀@個元素之后，這個組就空了，沒法貢獻(xiàn)給另外一個子序列了），且存在一個長度為 \(k+1\) 的上升子序列包含它。當(dāng)然如果不存在這個元素那就無解了。

使用樹狀數(shù)組維護(hù) LIS，時間復(fù)雜度 \(O(n\log n)\)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
#define mp make_pair
using namespace std;
const int maxn=2e5+10;
void cmin(int &x,int y){ x=x<y?x:y; }
void cmax(int &x,int y){ x=x>y?x:y; }
vector<int> vec; int ban[maxn];
int n,vis[maxn],p[maxn],f[maxn],g[maxn],cnt[maxn];
struct BIT{
	int c[maxn];
	int lowbit(int x){ return x&-x; }
	void init(){ for(int i=1;i<=n;i++) c[i]=0; }
	void modify(int x,int v){ for(;x<=n;x+=lowbit(x)) cmax(c[x],v); }
	int query(int x){ int res=0; for(;x;x-=lowbit(x)) cmax(res,c[x]); return res; }
}t;
void init(){ for(int i=1;i<=n;i++) vis[i]=cnt[i]=ban[i]=0; }
void solve(){
	cin>>n; init(); t.init(); int len=0;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		f[i]=t.query(p[i])+1; 
		t.modify(p[i],f[i]);
		cmax(len,f[i]);
	}
	if(len%2==0){
		cout<<"YES"<<endl;
		for(int i=1;i<=n;i++)
			if(f[i]<=len/2) cout<<0<<" ";
			else cout<<1<<" "; cout<<endl;
		return ;
	}
	t.init(); int k=(len+1)/2;
	for(int i=n;i>=1;i--){
		g[i]=t.query(n-p[i]+1)+1;
		t.modify(n-p[i]+1,g[i]); 
	}
	for(int i=1;i<=n;i++)
		if(f[i]+g[i]-1==len) cnt[f[i]]++;
	int id=0;
	for(int i=1;i<=n;i++){
		if(f[i]+g[i]-1==len&&cnt[f[i]]==1) continue;
		if(f[i]+g[i]-1>=k) id=i;
	}
	if(!id){ cout<<"NO"<<endl; return ; }
	cout<<"YES"<<endl; 
	int L=f[id]-min(f[id],k)+1,R=g[id]-(k-min(f[id],k));
	ban[f[id]]=1;
	int cur=f[id]-1; vis[id]=1;
	for(int i=id-1;i>=1&&cur>=L;i--)
		if(f[i]==cur) cur--,vis[i]=1,ban[f[i]]=1;
	cur=g[id]-1;
	for(int i=id+1;i<=n&&cur>=R;i++)
		if(g[i]==cur) cur--,vis[i]=1,ban[f[i]]=1;
	for(int i=1;i<=n;i++)
		if(vis[i]) cout<<0<<" ";
		else if(!ban[f[i]]) cout<<1<<" ";
		else if(f[i]==f[id]) cout<<1<<" ";
		else cout<<0<<" "; cout<<endl;
}
int main(){
	int T; cin>>T;
	while(T--) solve();
	return 0;
}