【启发式分裂】BZOJ4059 [Cerc2012]Non-boring sequences

题面在这里

​

启发式分裂裸题

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=200005;
int tst,n,m,a[maxn],b[maxn],L[maxn],R[maxn],lst[maxn];
bool solve(int l,int r){
	if (l>=r) return 1;
	for (int i=l,j=r;i<=j;i++,j--){
		if (L[i]<l&&r<R[i]) return solve(l,i-1)&&solve(i+1,r);
		if (L[j]<l&&r<R[j]) return solve(l,j-1)&&solve(j+1,r);
	}
	return 0;
}
int main(){
	scanf("%d",&tst);
	while (tst--){
		scanf("%d",&n);
		for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
		sort(b+1,b+1+n); m=unique(b+1,b+1+n)-b-1;
		for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
		for (int i=1;i<=m;i++) lst[i]=0;
		for (int i=1;i<=n;i++) L[i]=lst[a[i]],lst[a[i]]=i;
		for (int i=1;i<=m;i++) lst[i]=n+1;
		for (int i=n;i>=1;i--) R[i]=lst[a[i]],lst[a[i]]=i;
		if (solve(1,n)) puts("non-boring");else puts("boring");
	}
	return 0;
}