Description 我们害怕把这道题题面搞得太无聊了，所以我们决定让这题超短。一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。给定一个整数序列，请你判断它是不是不无聊的。
Input 第一行一个正整数T，表示有T组数据。每组数据第一行一个正整数n，表示序列的长度，1 <= n <= 200000。接下来一行n个不超过10^9的非负整数，表示这个序列。
Output 对于每组数据输出一行，输出"non-boring"表示这个序列不无聊，输出"boring"表示这个序列无聊。
代码
#include<map> #include<cstdio> #include<string> #define R_ register inline char gc() { static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read() { int ret=0,f=1,ch=gc(); for (; !isdigit(ch); ch=gc()) if (ch=='-') f=-f; for (; isdigit(ch); ch=gc()) ret=ret*10+ch-48; return ret*f; } const int maxn=2e5+5; std :: map <int,int> mp; int N,w,lst[maxn],nxt[maxn]; bool dfs(int L,int R) { if (L>=R) return 1; for (int i=L,j=R; i<=j; ) { if (lst[i]<=L&&nxt[i]>=R) return dfs(L,i-1)&&dfs(i+1,R);else ++i; if (lst[j]<=L&&nxt[j]>=R) return dfs(L,j-1)&&dfs(j+1,R);else --j; } return 0; } int main() { freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout); for (R_ int T=read(),i; T--; puts(dfs(1,N)?"non-boring":"boring")) { for (N=read(),mp.clear(),i=1; i<=N; ++i) lst[i]=nxt[i]=0; for (i=1; i<=N; mp[w]=i,++i) if (!mp[w=read()]) lst[i]=1; else nxt[mp[w]]=i-1,lst[i]=mp[w]+1; for (i=1; i<=N; ++i) if (!nxt[i]) nxt[i]=N; } return 0; }