题目:

我们害怕把这道题题面搞得太无聊了，所以我们决定让这题超短。一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。给定一个整数序列，请你判断它是不是不无聊的。

题解:

莫名其妙的暴力分治就可过。

不过网上貌似有证明这个分治的复杂度是\(O(n\log n)\)的。

至于怎么分治。。自己看代码吧。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

#define rg register int

#define rep(i,a,b) for(rg i=(a);i<=(b);++i)

#define per(i,a,b) for(rg i=(a);i>=(b);--i)

const int maxn = 200010;

int a[maxn],la[maxn],nx[maxn],ws[maxn];

int b[maxn];

inline bool check(int L,int R){

    if(L >= R) return true;

    int l = L,r = R,num = R-L+1;

    while(num--){

		if(num&1){

		    if(la[l] < L && nx[l] > R)

			return check(L,l-1) && check(l+1,R);

		    ++ l;

		}else{

		    if(la[r] < L && nx[r] > R)

			return check(L,r-1) && check(r+1,R);

		    -- r;

		}

    }return false;

}

int main(){

    int T;read(T);

    while(T--){

		int n;read(n);

		rep(i,1,n) read(a[i]),b[i] = a[i];

		sort(b+1,b+n+1);

		rep(i,1,n){

		     a[i] = lower_bound(b+1,b+n+1,a[i]) - b;

		     ws[i] = 0;

		}

		rep(i,1,n){

		    la[i] = ws[a[i]];

		    ws[a[i]] = i;

		}

		rep(i,1,n) ws[i] = n+1;

		per(i,n,1){

		    nx[i] = ws[a[i]];

		    ws[a[i]] = i;

		}

		if(check(1,n)) puts("non-boring");

		else puts("boring");

    }

    return 0;

}