一、题意

如果一个序列的任意连续子序列中至少有一个只出现一次的元素，则称这个序列是non-boring的。
输入一个长度为n的正整数序列（n<=200000），判断它是否是boring的。

二、解析

首先一起来学学语文：“任意连续子序列中至少有一个只出现一次的元素”.
这句话的反命题为：存在一个连续子序列，这个子序列中不存在只出现一次的元素。

因此我们首先在这个序列中找一个只出现一次的元素，若找不到，则序列是boring的。
若找到了，假设这个元素为a[p]，则包含这个元素的所有子序列都满足non-boring的条件了，剩下的子序列就都是a[0...p-1]的子序列或a[p+1,...n-1]的子序列了。
相信说到这大家都能发现，这里就出现了子问题了，因此这是我们用分治法就好了，当两个子问题a[0...p-1]和a[p+1,...n-1]都是non-boring的，原序列才是non-boring的。

这里我们需要用O(1)时间来判断一个元素在一个区间中是否是唯一的。要实现这个，我们首先得先进行预处理，得到原序列的l_same[i]数组和r_same[i]数组，他们分别表示以i为下标的元素左边和它位置最接近的相等的元素的下标，以及 右边和它位置最接近的相等的元素的下标。这个在输入时一并获取即可（具体见代码）。然后在后面我们在判断a[i]是否在a[l...r]是唯一的时候，就只需要判断l_same[i]和r_same[i]是否在[l...r]内即可。判断用时为O(1)。

还没完，我们分析一下时间复杂度，最坏情况下a[p]的位置在边缘，则时间复杂度满足T(n)=T(n-1)+O(n)，即为O(n^2)。这样是会超时的。原因就是我们无法确保a[p]的位置尽量在中间。

面对这个问题，紫薯给了我们提示：使用中途相遇法。
我们不要从左往右遍历寻找a[p]，而是从两边同时向中间遍历来寻找，这时如果a[p]在边缘，则时间复杂度满足T(n)=T(n-1)+O(1)，即为O(n)；若a[p]在中间，则时间复杂度满足T(n)=2T(n/2)+O(n)，即为O(nlgn)。这样就不会超时了。

三、代码

#include <iostream>
#include <unordered_map>
using namespace std;
const int maxn = 200000 + 5;
int kase, n, a[maxn], l_same[maxn], r_same[maxn];
unordered_map<int, int> pos;

// bool solve(int l, int r) {  // 该做法超时
//     if(l >= r) return 1;
//     int i = l;
//     for(; i < r; i ++) if(l_same[i] < l && r_same[i] > r) break;
//     if(i == r) return 0;
//     return solve(l, i - 1) && solve(i + 1, r);
// }

bool solve(int l, int r) {  // 通过中途相遇法避免超时
    if(l >= r) return 1;
    int i = l, j = r, p = -1;
    while(i <= j && p == -1) {
        if(l_same[i] < l && r_same[i] > r) p = i;
        else if(l_same[j] < l && r_same[j] > r) p = j;
        i ++, j --;
    }
    if(p == -1) return 0;
    return solve(l, p - 1) && solve(p + 1, r);
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n;
        pos.clear();
        fill(l_same, l_same + n + 1, -1);
        fill(r_same, r_same + n + 1, n);
        for(int i = 0; i < n; i ++) {
            cin >> a[i];
            if(pos.count(a[i])) {
                int prev_idx = pos[a[i]];
                l_same[i] = prev_idx, r_same[prev_idx] = i;
            }
            pos[a[i]] = i;
        }
        cout << (solve(0, n - 1) ? "non-boring" : "boring") << endl;
    }
}

四、归纳

  • 分治法：分而治之，将大问题分解为若干小问题，然后分到最小时的问题答案是能直接得到的。这种算法十分常见啊。需要好好掌握。
  • 中途相遇法：本题通过这个方法成功的降低了算法的最坏时间复杂度，我看了之后简直叹为观止。总之算是积累一下经验吧。
  • O(1)时间判断一个元素是否在一个区间内是唯一的：通过预处理得到l_same[maxn]和r_same[maxn]数组。他们分别表示以i为下标的元素左边和它位置最接近的相等的元素的下标，以及 右边和它位置最接近的相等的元素的下标。这个在输入时一并获取即可（具体见代码）。然后在后面我们在判断a[i]是否在a[l...r]是唯一的时候，就只需要判断l_same[i]和r_same[i]是否在[l...r]内即可。