好序列

题目描述：

给你一个数组a，问是否满足他的每个子区间[l,r]满足，至少存在一个元素x仅出现了一次

思路：

很有意思的一道题，到现在我还是迷迷糊糊的，无法理解真正理解这个复杂度是怎么算的

我们可以处理出来每个数字a[i]上一次出现的位置计作pre[i]，和下一次出现的位置nex[i]，显然对于(pre[i], nex[i])的区间，每个子区间的pre[i]<l<=i，i<=r<=nex[i]，都是满足至少存在一个元素仅出现一次

所以我们可以考虑分治，对于区间[l,r]，找到一个x,满足pre[x]<l&&nex[x]>r,则我们需要去计算区间[l,x-1]和[x+1,r]，如果这两个区间都符合条件，则这个整个的区间[l,r]是符合条件的，这就是一个简单的分治过程

但是如果直接让x从l枚举到r，则会超时，原因是如果每次的x都是在区间的最右边，那你每次都会遍历整个区间，而且下一个的区间长度是len-1,就会导致你的时间复杂度是 $O(n^2)$

我们可以考虑启发式分治，很玄学又非常科学

即我们从左边和右边同时进行枚举计算，这样每次的时间复杂度是最差的时候是x在最数组中间遇到，但是，有意思的是，在数组最中间的时候，你去dfs的两个区间的长度变成了原来的 $\frac{1}{2}$,所以如果每次都是最坏情况，最多进行log(n)次递归就结束了

所以时间复杂度总体上来说是O(nlogn)

具体证明不太会，只是一个感性和理性结合理解出来的想法

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define m_p(a, b) make_pair(a, b)

typedef long long ll;
typedef pair<int, int> pii;

#define MAX 1000050

int n, m, x;
int tr[MAX];
int pre[MAX];
int nex[MAX];

bool split(int l, int r){
    if(l>=r)return 1;
    for(int L=l, R=r; L<=R;++L,--R){
        if(pre[L]<l&&nex[L]>r)return split(l, L-1)&&split(L+1,r);
        if(pre[R]<l&&nex[R]>r)return split(R+1, r)&&split(l, R-1);
    }
    return false;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin>>tr[i];
    for(int i = 1; i <= n; ++i)pre[i]=-1, nex[i]=n+1;
    map<int, int>mp;
    for(int i = 1; i <= n; ++i){
        pre[i] = mp[tr[i]];
        nex[mp[tr[i]]] = i;
        mp[tr[i]] = i;
    }
    if(split(1,n))cout<<"non-boring\n";
    else cout<<"boring\n";
}

signed main(){
    io;
    int t;cin>>t;while(t--)
    work();
    return 0;
}