这个做法名字是从那里看到的……
Description
我们害怕把这道题题面搞得太无聊了，所以我们决定让这题超短。一个序列被称为是不无聊的，仅当它的每个连续子序列存在一个独一无二的数字，即每个子序列里至少存在一个数字只出现一次。给定一个整数序列，请你判断它是不是不无聊的。
Input
第一行一个正整数T，表示有T组数据。每组数据第一行一个正整数n，表示序列的长度，1 <= n <= 200000。接下来一行n个不超过10^9的非负整数，表示这个序列。
Output
对于每组数据输出一行，输出"non-boring"表示这个序列不无聊，输出"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
题目分析
颜色类的问题，处理$pre_i$和$nxt_i$算是一种套路吧。
考虑点$i$，它对于答案的贡献为$[l,r](l \in (pre_i,i],r \in [i,nxt_i))$。那么自然，如果数据结构强上就是线段树+扫描线二维数点。
但是有一种神奇的优秀（暴力）做法（）：我们注意到只要横跨$i$的区间就都是合法的。那么分治地考虑这个问题，$split(l,r)$表示$[l,r]$这个区间是否独立合法，转移时只需要找到一个$i$能够覆盖$[l,r]$就能拆分这个区间。
还要一点需要注意到的小细节（不过应该也是这类分治问题都存在的问题），寻找$i$的过程需要左右两边横跳，这样复杂度就能被控制在$T(n)=\max\{T(k)+T(n-k)+\min(k,n-k)\}=O(nlogn)$而不是$T(n)=\max\{T(k)+T(n-k)+n)\}=O(n^2)$
1 #include2 const int maxn = 200035; 3 4 int T,n,cnt; 5 int a[maxn],t[maxn],pre[maxn],nxt[maxn],lst[maxn]; 6 7 inline char nc() 8 { 9 static char buf[100000],*p1=buf,*p2=buf;10 if (p1==p2) {11 p2=(p1=buf)+fread(buf,1,100000,stdin);12 if (p1==p2) return EOF;13 }14 return *p1++;15 }16 #define getchar nc17 int read()18 {19 char ch = getchar();20 int num = 0;21 bool fl = 0;22 for (; !isdigit(ch); ch=getchar())23 if (ch=='-') fl = 1;24 for (; isdigit(ch); ch=getchar())25 num = (num<<1)+(num<<3)+ch-48;26 if (fl) num = -num;27 return num;28 }29 bool split(int l, int r)30 {31 if (l >= r) return 1;32 int x = l, y = r;33 for (int i=l; i<=r; i++)34 if (i&1){35 if (pre[x] < l&&nxt[x] > r)36 return split(l, x-1)&&split(x+1, r);37 x++;38 }else{39 if (pre[y] < l&&nxt[y] > r)40 return split(l, y-1)&&split(y+1, r);41 y--;42 }43 return 0;44 }45 int main()46 {47 T = read();48 while (T--)49 {50 cnt = n = read();51 memset(lst, 0, n<<2);52 memset(pre, 0, n<<2);53 memset(nxt, 0, n<<2);54 for (int i=1; i<=n; i++) t[i] = a[i] = read();55 std::sort(t+1, t+n+1);56 cnt = std::unique(t+1, t+n+1)-t-1;57 for (int i=1; i<=n; i++){58 a[i] = std::lower_bound(t+1, t+cnt+1, a[i])-t;59 nxt[lst[a[i]]] = i, pre[i] = lst[a[i]];60 lst[a[i]] = i, nxt[i] = n+1;61 }62 puts(split(1, n)?"non-boring":"boring");63 }64 return 0;65 }
END