题目传送门(BZOJ)

题解 :

分治
考虑一段区间 (l, r), 若这个区间中有某个数字 x 使得它在整段区间中的出现次数为 1,
那么对于所有包含这个数字的子区间, 该数都有且仅有一次出现, 所以只需要分治它两边的区间即可
如果这个区间中没有这样的数, 那么这个区间不合法

求这样的一个数就是求某数上一次出现在 l 之前, 下一次出现在 r 之后, 我们先离散化一下, 然后用链表直接预处理出来这个即可
又由于这个数字不是恰好出现在区间中点, 故我们要从两侧同时向中点扫, 这样的复杂度一定是 O(2\times len_{short}) 的,
len_{short} 必然小于等于区间长度一半

这个思想似乎应该叫启发式分裂 ?
复杂度 O(T\times N\log N)
请注意, 由于数据组数可能很大, 不能用 memset 来清空数组

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 201000;#define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++char buf[100000], *p1, *p2;inline char gc() { char ch = nc(); while(isspace(ch)) ch = nc(); return ch;}inline int rd() { int x = 0, f = 1; char ch = nc(); while(!isdigit(ch)) ch = nc(); while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc(); return x*f;}int T, n, a[N], v[N];int L[N], R[N], H[N];bool Solve(int l, int r) { if(l > r) return true; int mid = 0; for(int i = l; i <= (l+r) >> 1 && mid == 0; i ++ ) { if(L[i] < l && R[i] > r) mid = i; if(L[l+r-i] < l && R[l+r-i] > r) mid = l+r-i; } if(mid) return Solve(l, mid-1) && Solve(mid+1, r); return 0;}int main() { T = rd(); while(T -- ) { n = rd(); for(int i = 1; i <= n; i ++ ) v[i] = a[i] = rd(), H[i] = L[i] = 0, R[i] = n+1; sort(v+1, v+n+1); for(int i = 1; i <= n; i ++ ) a[i] = lower_bound(v+1, v+n+1, a[i])-v, L[i] = H[a[i]], R[L[i]] = i, H[a[i]] = i; if(Solve(1, n)) printf("non-"); puts("boring"); }}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<