[Cerc2012]Non-boring sequences

Description

定义一个序列是不无聊的，当且仅当它的所有子区间都存在一个独一无二的数字，即每个子区间里至少存在一个数字只出现过一次。给定一个长度为(N(Nleq2 imes 10^5))的序列，请判断它是不是无聊的。

Solution

对于每个位置(i)，先求出(pre[i],nxt[i])表示在(i)之前第一个和在(i)之后第一个权值等于(val[i])的位置。

如果一个区间([l,r])不是无聊的，一个必要条件是存在(iin [l,r])满足(pre[i]<l;land ;nxt[i]>r)。这样所有跨过(i)的区间都是不无聊的，接着判断([l,i))和((i,r])就行了。

这启发我们分治解决问题。

每次在([l,r])内找到一个满足上述条件的(i)，然后递归处理两边的区间。

复杂度看上去貌似很爆炸，因为没有每次从中间切开的话就不能保证递归层数是(O(log))级别了。

然而有个很玄妙的结论是(T(n)=maxleft{ T(k)+T(n-k)+min(k,n-k) ight}approx O(nlog n))

这里证明写的很清晰。

说到底，我们不断拆分这个过程，分开后就不会再合并，而且每次拆开的复杂度就是拆成的两个序列中较小的一个，很自然地想到把这个过程倒过来，那么这就是一个启发式合并的过程，显然时间复杂度就是(O(nlog n))啦

所以我们从两边向中间扫，如果遇到了第一个满足上述条件的 (i) 就在这里递归下去。

本地记得开栈！

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
"):printf("boring
");
    } return 0;
}