定义一个序列是不无聊的，当且仅当它的所有子区间都存在一个独一无二的数字，即每个子区间里至少存在一个数字只出现过一次。给定一个长度为\(N(N\leq2\times 10^5)\)的序列，请判断它是不是无聊的。
Solution对于每个位置\(i\)，先求出\(pre[i],nxt[i]\)表示在\(i\)之前第一个和在\(i\)之后第一个权值等于\(val[i]\)的位置。
如果一个区间\([l,r]\)不是无聊的，一个必要条件是存在\(i\in [l,r]\)满足\(pre[i]<l\;\land \;nxt[i]>r\)。这样所有跨过\(i\)的区间都是不无聊的，接着判断\([l,i)\)和\((i,r]\)就行了。
这启发我们分治解决问题。
每次在\([l,r]\)内找到一个满足上述条件的\(i\)，然后递归处理两边的区间。
复杂度看上去貌似很爆炸，因为没有每次从中间切开的话就不能保证递归层数是\(O(\log)\)级别了。
然而有个很玄妙的结论是\(T(n)=max\left\{ T(k)+T(n-k)+min(k,n-k)\right\}\approx O(n\log n)\)
这里证明写的很清晰。
说到底，我们不断拆分这个过程，分开后就不会再合并，而且每次拆开的复杂度就是拆成的两个序列中较小的一个，很自然地想到把这个过程倒过来，那么这就是一个启发式合并的过程，显然时间复杂度就是\(O(n\log n)\)啦
本地记得开栈！
Code #include<set> #include<map> #include<cmath> #include<queue> #include<cctype> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using std::min; using std::max; using std::swap; using std::vector; const int N=2e5+5; typedef double db; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define mp(A,B) std::make_pair(A,B) int n,val[N],las[N]; int nxt[N],pre[N],g[N]; int getint(){ int X=0,w=0;char ch=0; while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } bool solve(int l,int r){ if(l>r) return 1; if(l==r) return 1; for(int i=l;i<=r;i++){ if(pre[i]<l and nxt[i]>r) return solve(l,i-1) and solve(i+1,r); } return 0; } signed main(){ int T=getint(); while(T--){ int n=getint(); for(int i=1;i<=n;i++) g[i]=val[i]=getint(); std::sort(g+1,g+1+n);int len=std::unique(g+1,g+1+n)-g-1; for(int i=1;i<=n;i++){ val[i]=std::lower_bound(g+1,g+1+len,val[i])-g; pre[i]=las[val[i]];las[val[i]]=i; } for(int i=1;i<=len;i++) las[i]=n+1; for(int i=n;i;i--){ nxt[i]=las[val[i]]; las[val[i]]=i; } for(int i=1;i<=len;i++) las[i]=0; solve(1,n)?printf("non-boring\n"):printf("boring\n"); } return 0; }