We were afraid of making this problem statement too boring, so we decided to keep it short. A sequence
is called non-boring if its every connected subsequence contains a unique element, i.e. an element such
that no other element of that subsequence has the same value.
Given a sequence of integers, decide whether it is non-boring.
Input
The first line of the input contains the number of test cases T. The descriptions of the test cases follow:
Each test case starts with an integer n (1 ≤ n ≤ 200000) denoting the length of the sequence. In
the next line the n elements of the sequence follow, separated with single spaces. The elements are
non-negative integers less than 109.
Output
Print the answers to the test cases in the order in which they appear in the input. For each test case
print a single line containing the word ‘non-boring’ or ‘boring’.
Sample Input
4
5
1 2 3 4 5
5
1 1 1 1 1
5
1 2 3 2 1
5
1 1 2 1 1
Sample Output
non-boring
boring
non-boring
boring
题意:一个序列被称作是不无聊的,当且仅当,任意一个连续子区间,存在一个数字只出现了一次,问给定序列是否是不无聊的。
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
int a[maxn],pre[maxn],lat[maxn];
map<int,int>mp;
bool check(int L,int R){
if(L>=R) return true;
int l=L,r=R;
for(int i=L;i<=R;i++){
if(i&1){
if(pre[l]<L&&lat[l]>R) return check(L,l-1)&&check(l+1,R);
l++;
}
else{
if(pre[r]<L&&lat[r]>R) return check(L,r-1)&&check(r+1,R);
r--;
}
}
return false;
}
int main(){
int t; scanf("%d",&t);
while(t--){
mp.clear();
int n; scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
lat[mp[a[i]]]=i;
pre[i]=mp[a[i]];
mp[a[i]]=i;
}
for(int i=1;i<=n;i++) lat[mp[a[i]]]=n+1;
if(check(1,n)) puts("non-boring");
else puts("boring");
}
return 0;
}