UVa1608 Non-boring sequences（尺取+分治）

题目链接

1.题目大意：如果一个序列的任意连续子序列中至少有一个只出现一次的元素，则称这个序列是不无聊的。判断输入的序列是否为不无聊的

2.首先想到整体思路：在序列[l,r]中如果能找到一个只出现一次的元素，设其位置为p，那么只需要继续检查序列[l,p-1]和[p+1,r]。不难证明这个结论是正确的：首先满足大区间，接着在不考虑满足大区间的一个只出现一次的元素，如果两个子区间能找到满足的元素那么就继续分治考虑更小的区间，直到区间长度小于等于1。但是如何某个元素在这段序列是唯一？事先算出每个元素左边和右边最近的元素下标保存，设用L和R两数组保存，那么判断时只需要判断元素的L和R是否超过该区间就行。至于具体如何保存，使用map不断从左到右（从右到左）更新每个元素对应下标即可。还有一个注意点，L初始化为0，R初始化为INF

3.本题的时间复杂度的计算很经典，首先如果从右向左判断每个数是否唯一的话，最坏的话唯一的数都在最右边，那么时间复杂度为O(n²)，从右向左同理。如果设置两个指针，分别从左和右开始向中间找，最坏的情况下每次都在中间找到，这样的话T(n)=2*T(n-1)+O(n)，最坏的时间复杂度O(n*logn)，实际上中途相遇法也是尺取的一种，算是双指针，和回文串的判断思想一致

4.需要注意使用memset初始化数组会超时，因此在两次反向遍历求L和R时也能更新为0或INF

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=2e5+10;
int a[maxn],L[maxn],R[maxn];
unordered_map<int,int> mp;

bool solve(int l,int r){
    if(l>=r) return true;
    for(int i=l,j=r;i<=j;i++,j--){
        if(L[i]<l && R[i]>r) return solve(l,i-1) && solve(i+1,r);
        if(L[j]<l && R[j]>r) return solve(l,j-1) && solve(j+1,r);
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        mp.clear();
        //memset(L,0,sizeof L);
        //memset(R,0x3f,sizeof R);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(!mp[a[i]]) L[i]=0;
            else L[i]=mp[a[i]];
            mp[a[i]]=i;
        }
        mp.clear();
        for(int i=n;i>=1;i--){
            if(!mp[a[i]]) R[i]=INF;
            else R[i]=mp[a[i]];
            mp[a[i]]=i;
        }
        if(solve(1,n)) cout<<"non-boring"<<endl;
        else cout<<"boring"<<endl;
    }
    return 0;
}