题目概述

判断一个序列是否满足所有子序列都有一个数只出现了一次。

解题报告

可以用矩形覆盖+扫描线的方法，不过可以像NWERC2017F一样启发式分裂。

一个数左边第一个相同的数和右边第一个相同的数这一段肯定满足，如果某一个数 $x$ 覆盖了 $[L,R]$ 那么就可以分治做 $[L,x-1],[x+1,R]$ 了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200000;

int te,n,a[maxn+5],tem[maxn+5],lst[maxn+5],pre[maxn+5],nxt[maxn+5];

inline int Find(int x,int L=1,int R=tem[0]){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        if (tem[mid]==x) return mid; else x<tem[mid]?R=mid-1:L=mid+1;
}
bool Dfs(int L,int R){
    if (L>R) return true;
    for (int l=L,r=R;l<=r;l++,r--){
        if (R<=nxt[l]&&pre[l]<=L) return Dfs(L,l-1)&&Dfs(l+1,R);
        if (R<=nxt[r]&&pre[r]<=L) return Dfs(L,r-1)&&Dfs(r+1,R);
    }return false;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),tem[i]=a[i];
        sort(tem+1,tem+1+n);tem[0]=unique(tem+1,tem+1+n)-tem-1;for (int i=1;i<=n;i++) a[i]=Find(a[i]);
        for (int i=1;i<=tem[0];i++) lst[i]=0;for (int i=1;i<=n;lst[a[i]]=i,i++) lst[a[i]]?pre[i]=lst[a[i]]+1:pre[i]=1;
        for (int i=1;i<=tem[0];i++) lst[i]=0;for (int i=n;i>=1;lst[a[i]]=i,i--) lst[a[i]]?nxt[i]=lst[a[i]]-1:nxt[i]=n;
        puts(Dfs(1,n)?"non-boring":"boring");
    }
    return 0;
}