UVA 1608 Non-boring sequence 不无聊的序列（分治，中途相遇）

题意：给你一个长度为n序列，如果这个任意连续子序列的中都有至少出现一次的元素，那么就称这个序列是不无聊的，判断这个序列是不是无聊的。

先预处理出每个元素之前和之后相同元素出现的位置，就可以在O(1)的时间判断出一个元素在一个区间内是否唯一。

每次从大的序列中找一个唯一元素，包含这个元素的就不用判断了，那么以这个元素为分界线，在分别判断两边的序列。

如果只从一遍找的话，最坏的情况是唯一元素在另一头T(n) = T(n-1)+O(n) >= O(n^2)的。

所以应该从两边开始找，T(n) = 2T(n/2)+O(n)， 渐进复杂度是O(nlogn)。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+42;
#define se second
int a[maxn];
int pre[maxn];
int aft[maxn];
map<int,int>mp;

#define CheckUnique(k)
if(pre[k]<L&&aft[k]>R) return check(L,k-1)&&check(k+1,R)

bool check(int L,int R)
{
    if(L>=R) return true;
    int i = L,j = R;
    while(i<=j){
        CheckUnique(i);
        CheckUnique(j);
        i++;j--;
    }
    return false;
}

int main()
{
   // freopen("in.txt","r",stdin);
    int T; scanf("%d",&T);
    while(T--){
        int n; scanf("%d",&n);
        mp.clear();
        map<int,int>::iterator it;
        memset(aft,0x3f,sizeof(int)*n);
        for(int i = 0; i < n; i++){
            scanf("%d",a+i);
            if(it = mp.find(a[i]),it!=mp.end()){
                pre[i] = it->se;
                aft[it->se] = i;

            }else {
                pre[i] = -1;
            }
            mp[a[i]] = i;
        }
        if(check(0,n-1)) printf("non-");
        printf("boring
");
    }
    return 0;
}