我们害怕把这道题题面搞得太无聊了，所以我们决定让这题超短。一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。给定一个整数序列，请你判断它是不是不无聊的。
第一行一个正整数T，表示有T组数据。每组数据第一行一个正整数n，表示序列的长度，1 <= n <= 200000。接下来一行n个不超过10^9的非负整数，表示这个序列。
对于每组数据输出一行，输出"non-boring"表示这个序列不无聊，输出"boring"表示这个序列无聊。
鸣谢Tjz
[ Submit][ Status][ Discuss] 对于区间[L,R]，假设位置k的数字在这个区间中只出现过一次 那么所有左端点∈[L,k-1]，右端点∈[k+1,R]的区间都不无聊 若所有左右端点∈[L,k-1]以及左右端点∈[k+1,R]的区间也不无聊，那么[L,R]的所有子区间就都不无聊了 这样就可以通过分治解决，从[1,n]开始，每次从两边向中间找，找到这样的数字就分成两段 下面证明一下这样分治的复杂度 假设T([L,R])为判定[L,R]的子区间是否无聊的复杂度 对于当前这一层，左右都找了k次才找到这个数字，因此T([L,R]) = T([L,k-1]) + T([k+1,R]) + O(k) 不妨称找到的这样的数字为关键数字 那么每个关键数字在递归过程中出现，序列的长度就至少增长了两倍 每个数字总是会充当一次关键数字，因此总复杂度是O(nlogn) #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 2E5 + 20; int n,T,cur,A[maxn],B[maxn],last[maxn],pre[maxn],nex[maxn]; bool Judge(int l,int r) { if (l >= r) return 1; int mid = l + r >> 1; for (int i = l,j = r; i <= mid || j > mid; i++,j--) if (pre[i] < l && r < nex[i]) { if (!Judge(l,i - 1)) return 0; return Judge(i + 1,r); } else if (pre[j] < l && r < nex[j]) { if (!Judge(l,j - 1)) return 0; return Judge(j + 1,r); } return 0; } int getint() { char ch = getchar(); int ret = 0; while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') ret = ret * 10 + ch - '0',ch = getchar(); return ret; } void Solve() { n = getint(); cur = 1; for (int i = 1; i <= n; i++) A[i] = B[i] = getint(); sort(B + 1,B + n + 1); for (int i = 2; i <= n; i++) if (B[i] != B[i - 1]) B[++cur] = B[i]; for (int i = 1; i <= cur; i++) last[i] = 0; for (int i = 1; i <= n; i++) { A[i] = lower_bound(B + 1,B + cur + 1,A[i]) - B; pre[i] = last[A[i]]; last[A[i]] = i; } for (int i = 1; i <= cur; i++) last[i] = n + 1; for (int i = n; i; i--) nex[i] = last[A[i]],last[A[i]] = i; puts(Judge(1,n) ? "non-boring" : "boring"); } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif T = getint(); while (T--) Solve(); return 0; }