题目：
分析：
想了半天没什么想法，百度到一个神仙做法……
设原数列为 (a)，对于每一个 (i) 求出前一个和后一个和 (a_i) 相等的位置 (pre[i]) 和 (nxt[i]) （如果不存在则分别为 (-1) 和 (n+1) ）。那么如果在一个区间 ([l, r]) 中存在一个 (i) 满足 (pre[i]<l) 且 (nxt[i]>r) ，说明 (i) 在 ([l, r]) 中只出现了一次，那么任意一个跨越 (i) 的 ([l, r]) 的子区间都是不无聊的，只需要再判断 ([l, i)) 和 ((i, r]) 中是否存在这样的 (i) 即可。
(i) 从两边往中间暴力找（绝对不能从左往右暴力扫一遍！！，那样复杂度就高了），复杂度是 (O(nlog n)
)没想到吧！。
下面来证明（感性理解）一下这个神奇的复杂度。正着想比较麻烦，我们倒过来。把递归调用的树画出来（很显然是个二叉树），然后从下往上看，把分治倒过来变成向上合并。每次合并是一个长为 (l_1) 的区间和一个长为 (l_2) 的区间合起来变成一个长为 (l_1+l_2+1) 的区间。而这次合并所花的时间是从两端点暴力找 (i) 的时间，即 (min(l_1, l_2)) （当然还要乘个 (2) 之类，但那不影响复杂度）。这个过程是不是很像启发式合并？于是时间复杂度 (O(nlog n))
代码：
思路清晰，解法自然
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
namespace zyt
{
template<typename T>
inline bool read(T &x)
{
char c;
bool f = false;
x = 0;
do
c = getchar();
while (c != EOF && c != '-' && !isdigit(c));
if (c == EOF)
return false;
if (c == '-')
f = true, c = getchar();
do
x = x * 10 + c - '0', c = getchar();
while (isdigit(c));
if (f)
x = -x;
return true;
}
template<typename T>
inline void write(T x)
{
static char buf[20];
char *pos = buf;
if (x < 0)
putchar('-');
do
*pos++ = x % 10 + '0';
while (x /= 10);
while (pos > buf)
putchar(*--pos);
}
inline void write(const char *const s)
{
printf("%s", s);
}
const int N = 2e5 + 10;
int T, n, arr[N], tmp[N], last[N], nxt[N], pre[N];
bool check(const int l, const int r)
{
if (l > r)
return true;
int tmpl = l, tmpr = r;
for (int i = 0; i < (r - l + 1); i++)
if (i & 1)
{
if (pre[tmpl] < l && nxt[tmpr] > r)
return check(l, tmpl - 1) && check(tmpl + 1, r);
++tmpl;
}
else
{
if (pre[tmpr] < l && nxt[tmpr] > r)
return check(l, tmpr - 1) && check(tmpr + 1, r);
--tmpr;
}
return false;
}
int work()
{
read(T);
while (T--)
{
read(n);
for (int i = 0; i < n; i++)
read(arr[i]), tmp[i] = arr[i];
sort(tmp, tmp + n);
int cnt = unique(tmp, tmp + n) - tmp;
for (int i = 0; i < n; i++)
arr[i] = lower_bound(tmp, tmp + cnt, arr[i]) - tmp;
memset(last, -1, sizeof(int[cnt]));
for (int i = 0; i < n; i++)
{
if (~last[arr[i]])
nxt[last[arr[i]]] = i;
pre[i] = last[arr[i]];
last[arr[i]] = i;
}
for (int i = 0; i < cnt; i++)
nxt[last[i]] = n + 1;
if (check(0, n - 1))
write("non-boring
");
else
write("boring
");
}
return 0;
}
}
int main()
{
return zyt::work();
}