题目大意：
对一个序列，如果其任意子区间都有至少一个数只出现一次，那么则称这个序列为non-boring的，否则为boring
思路：
- 中 数 只出现一次, 极值对关于区间的点对问题,可以通过这个点把区间分成2个部分,分治解决
- 预处理每个数上一次出现的位置以及下一次出现的位置
- 对一个区间，如果有一个数满足条件，则以这个数为分界点，对两边进行分治
- 在枚举满足条件的分界点时从区间两边向中间进行枚举,这样只枚举了n/2
- 使本身可能成为On的算法优化到Onlogn
- 大致证明可由 T(n) = 2 * T(n/2) + O(n) 得到
#include <iostream> #include <algorithm> #include <map> #include <cstdio> using namespace std; const int maxn= 200000+5; int a[maxn]; int l[maxn],r[maxn]; map<int,int> m; int n; bool judge(int left,int right) { if(left>=right) return true; for(int i=0;i<=(right-left)/2;i++) { if(l[left+i]<left && r[left+i]>right) return judge(left,left+i-1)&&judge(left+i+1,right); if(l[right-i]<left && r[right-i]>right) return judge(left,right-i-1)&&judge(right-i+1,right); } return false; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",a+i); //记录第i个元素左边第一个相同元素的位置 m.clear(); for(int i=0;i<n;i++) { if(m.count(a[i])) l[i]=m[a[i]]; else l[i]=-1; m[a[i]]=i; } //记录第i个元素右边第一个相同元素的位置 m.clear(); for(int i=n-1;i>=0;i--) { if(m.count(a[i])) r[i]=m[a[i]]; else r[i]=n; m[a[i]]=i; } if(judge(0,n-1)) cout<<"non-boring"<<endl; else cout<<"boring"<<endl; } return 0; }