题目描述
我们害怕把这道题题面搞得太无聊了，所以我们决定让这题超短。一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。给定一个整数序列，请你判断它是不是不无聊的。
输入
第一行一个正整数T，表示有T组数据。每组数据第一行一个正整数n，表示序列的长度，1 <= n <= 200000。接下来一行n个不超过10^9的非负整数，表示这个序列。
输出
对于每组数据输出一行，输出"non-boring"表示这个序列不无聊，输出"boring"表示这个序列无聊。
样例输入
4
5
1 2 3 4 5
5
1 1 1 1 1
5
1 2 3 2 1
5
1 1 2 1 1
样例输出
non-boring
boring
non-boring
boring
题解
分治
考虑一段区间：
如果这个区间中存在某个数，使得它在整段区间中出现次数为1，那么对于所有包含该数的子区间，该数都出现且仅出现1次。所以只需要分治处理这个数左右两端的子区间即可。
如果这个区间中不存在这样的数，那么它就是不合法的。
于是只需要想办法求出区间中只出现过一次的数即可。一个数在区间中只出现过1次，当且仅当它上一次出现的位置在区间左端，下一次出现的位置在区间右端。所以预处理左右出现的位置即可判断。
由于这个数不是恰好出现在区间中间的，所以找一次的时间复杂度应该设计为$O(较小的一段子区间的长度)$。具体方法：从左右两端向中间扫，扫到了就停止。这样找一次的复杂度一定是2倍较短区间长度。
时间复杂度为$O(n\log n)$。
注意由于有多组数据，数组需要动态清空，不能使用memset。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
using namespace std;
int a[N] , v[N] , pos[N] , lp[N] , rp[N];
bool solve(int l , int r)
{
if(l > r) return 1;
int i , mid = 0;
for(i = l ; i <= (l + r) >> 1 ; i ++ )
{
if(lp[i] < l && rp[i] > r) mid = i;
if(lp[l + r - i] < l && rp[l + r - i] > r) mid = l + r - i;
if(mid) break;
}
if(mid) return solve(l , mid - 1) && solve(mid + 1 , r);
else return 0;
}
int main()
{
int T;
scanf("%d" , &T);
while(T -- )
{
int n , i;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , v[i] = a[i] , pos[i] = lp[i] = 0 , rp[i] = n + 1;
sort(v + 1 , v + n + 1);
for(i = 1 ; i <= n ; i ++ ) a[i] = lower_bound(v + 1 , v + n + 1 , a[i]) - v , lp[i] = pos[a[i]] , rp[lp[i]] = i , pos[a[i]] = i;
if(solve(1 , n)) printf("non-");
puts("boring");
}
return 0;
}