uva 1608 不无聊的序列（附带常用算法设计和优化策略总结）
紫书上有这样一道题：
如果一个序列的任意连续子序列中都至少有一个只出现一次的元素，则称这个序列时不无聊的。输入一个n个元素的序列，判断它是不是无聊的序列。n<=200000。
首先，在整个序列中找到只出现一次的元素ai。如果不能找到，那它就是无聊的。不然，就可以退出当前循环，递归判断[1, i-1]和[i+1, n]是不是无聊的序列。然而怎么找ai很重要。如果从一头开始找，那么最差情况下的时间复杂度就是O(n^2)的。而如果从两头开始找，那么最差情况就变成了ai在中间，时间复杂度是O(nlogn)！这是因为在中间的找起来慢，分起来快，而在两端的找起来快，分起来慢。有些时候用好中途相遇法还是很重要的！
下面是紫书上讲的常用算法设计策略和优化策略（注意这里是设计策略而不是算法）：
构造法（构造解），
中途相遇法（通常比多个相遇法还要优秀），
问题分解（将两个不相关的问题剥离开来分别求解），
等价转换（化繁为简），
假设法（利用对称性避免讨论），
使用数据结构（在不改变主算法的情况下加速算法），
数形结合（通常与滑动窗口相联系），
二分答案（将求最优值转化为判定最优值，也算在策略内），
扫描法（带有顺序的枚举法，通常维护一些重要的量），
枚举基准（寻找基于当前基准的最优值，再取所有基准的最值），
滑动窗口（维护单调性，高效去除冗余状态）等等。