题目：
分析：
想了半天没什么想法，百度到一个神仙做法……
设原数列为 \(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(n\log n)
\)没想到吧！。
下面来证明（感性理解）一下这个神奇的复杂度。正着想比较麻烦，我们倒过来。把递归调用的树画出来（很显然是个二叉树），然后从下往上看，把分治倒过来变成向上合并。每次合并是一个长为 \(l_1\) 的区间和一个长为 \(l_2\) 的区间合起来变成一个长为 \(l_1+l_2+1\) 的区间。而这次合并所花的时间是从两端点暴力找 \(i\) 的时间，即 \(min(l_1, l_2)\) （当然还要乘个 \(2\) 之类，但那不影响复杂度）。这个过程是不是很像启发式合并？于是时间复杂度 \(O(n\log 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\n");
else
write("boring\n");
}
return 0;
}
}
int main()
{
return zyt::work();
}