题意：如果一个序列的任意连续子序列中至少有一个只出现一次的元素，则称这个序列式不无聊（non-boring）的。输入一个n
(
n
≤
200000
)
个元素的序列A（各个元素均为
10
9
以内的非负整数），判断它是不是不无聊的。（本段摘自《算法竞赛入门经典（第2版）》
分析：
首先预处理每个元素向左向右分别能延伸到什么地方，然后采用分治的思想，对于一段序列，首先去寻找只出现一次的元素，假设为a[i]，然后分别递归处理a[i]左边和右边的序列，处理完即可。
需要注意的是，在寻找只出现一次的元素是，要从两边同时开始找，这样最坏情况的复杂度为
O
(
n
l
o
g
n
)
，如果只从一边找的话，最坏情况复杂度为
O
(
n
2
)
。
代码：
#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <sstream>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int maxn = 200000 + 5;
int T, n;
int a[maxn], l[maxn], r[maxn], pos[maxn];
bool DFS(int L, int R)
{
if (L + 1 >= R)
return true;
for (int i = L; i < R; ++i)
{
if (l[i] < L && r[i] >= R)
return DFS(L, i) && DFS(i + 1, R);
if (l[R - (i - L) - 1] < L && r[R - (i - L) - 1] >= R)
return DFS(L, R - (i - L) - 1) && DFS(R - (i - L) - 1 + 1, R);
}
return false;
}
int main()
{
scanf("%d", &T);
for (int C = 0; C < T; ++C)
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
for (int i = 0; i < n; ++i)
pos[i] = -1;
for (int i = 0; i < n; ++i)
{
l[i] = pos[a[i]];
pos[a[i]] = i;
}
for (int i = 0; i < n; ++i)
pos[i] = n;
for (int i = n - 1; i >= 0; --i)
{
r[i] = pos[a[i]];
pos[a[i]] = i;
}
if (DFS(0, n))
printf("non-boring\n");
else
printf("boring\n");
}
return 0;
}