Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom8月前

12/11
13:44
暴力

[bzoj 4059] [Cerc2012]Non-boring sequences

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 我们害怕把这道题题面搞得太无聊了,所以我们决定让这题超短。一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个正整数T,表示有T组数据。每组数据第一行一个正整数n,表示序列的长度,1 <= n <= 200000。接下来一行n个不超过10^9的非负整数,表示这个序列。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每组数据输出一行,输出"non-boring"表示这个序列不无聊,输出"boring"表示这个序列无聊。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

non-boring
boring
non-boring
boring

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

如果我们要验证[l,r]这个区间是否满足要求,那么假如找到了一个位置x是唯一出现的,那么只要继续验证[l,x-1]和[x+1,r]就可以了。

如何判断一个数是否在一个区间中只出现过一次,先预处理出它左边和右边离它距离最近的相同的点,假如是ls[i]和rs[i],那么只要保证ls[i]<l&&rs[i]>r就能保证a[i]这个数在[l,r]中只出现过一次了,这个可以离散化后解决。

然后我们从两边往中间扫找出第一个唯一出现的数,时间复杂度就是

T(n)=max{T(k)+T(n-k)+min(k,n-k)}=O(nlogn)

可以用归纳法证明

 

[bzoj 4059] [Cerc2012]Non-boring sequences