BZOJ 4059 [Cerc2012]Non-boring sequences

发布于 2017-08-14  195 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4059

题意:一个序列被称为是不无聊的,仅当它的每个连续子序列存在一个独一无二的数字,即每个子序列里至少存在一个数字只出现一次。给定一个整数序列,请你判断它是不是不无聊的。


妙啊~妙啊...

首先考虑最基础的暴力:枚举每个区间是否合法——>\(O(n^3)\)

稍优一些地:如果我们知道每个数的合法区间(即这个数作为独一无二的数字的最大区间),就可以 O(1) 的判断这个数是否可以作为“分隔数”(即所有横跨这个数的区间都是合法的,可以递归的去判断两侧的区间)。

那么这样的话,从左至右的枚举,如果每次分隔都只能使得一个数合法,就会退化为\(O(n^2)\)

转换一下思想,从左右同时向中间枚举,最坏的的情况只能是从中间分隔开,就是\(O(nlog_n)\) 的了。

真是奥妙重重啊...

 


一个非常弱的准退役OIER