BZOJ4059 - Click Here
Description
我们害怕把这道题题面搞得太无聊了，所以我们决定让这题超短。一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。给定一个整数序列，请你判断它是不是不无聊的。
Input
第一行一个正整数T，表示有T组数据。每组数据第一行一个正整数n，表示序列的长度，1 <= n <= 200000。接下来一行n个不超过10^9的非负整数，表示这个序列。
Output
对于每组数据输出一行，输出”non-boring”表示这个序列不无聊，输出”boring”表示这个序列无聊。
Solutions
注意到对于区间$[L,R]$，如果存在一个元素$k$，在区间$[L,R]$内是唯一的，那么跨过$k$的区间必定是不无聊的。因此这个问题就转换成判断区间$[L,k-1]$和区间$[k+1,R]$是不是无聊区间。而一个元素是否是唯一的，能够通过记录该元素的前后继$O(1)$得知。
如果暴力执行这个操作，其时间复杂度为$T(n)=T(k)+T(n-k)+O(n)$，最坏情况下能到达$O(n^2)$。
考虑进行一点小小的优化。将每次暴力寻找区间内唯一的元素，改成每次从外侧到内侧寻找唯一的元素。此时时间复杂度为$T(n)=T(k)+T(n-k)+min(n-k,k)$。这个过程可以看做是启发式合并的逆过程(反过来看，每个元素至多会被合并$\log n$)，因此时间复杂度为$O(n \, \log n)$。
CODE
CODE - Click Here