UVA1608 Non-boring sequences【启发式分治】

题意:

如果一个序列的任意连续子序列都至少有一个元素唯一，则称这个序列“不无聊”，否则称这个序列“无聊”。给定T个序列，求是否“无聊”。
国内vjudge链接

思路:

先做一次预处理把每一个元素前一次出现的相同元素的值的位置和后一次出现的相同元素的值的位置记录下来
每次找到一个只出现了一次的点，其位置的pos，那么继续分治[L,pos-1]，[pos1+1,R]
为了保证时间复杂度，每一次找pos要从两边往中间找

AC_code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
int a[maxn], pre[maxn], nxt[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 && nxt[l] > R) {
				return check(L, l-1)&&check(l+1, R);
			}
			l++;
		} else {
			if(pre[r] < L && nxt[r] > R) {
				return check(L, r-1)&&check(r+1, R);
			}
			r--;
		}
	}
	return false;
}
int main() {
	int n, t;
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		mp.clear();
		for(int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			nxt[mp[a[i]]] = i;
			pre[i] = mp[a[i]];
			mp[a[i]] = i;
		}
		for(int i = 1; i <= n; i++) {
			nxt[mp[a[i]]] = n+1;//每种点的最后一个点
		}
		if(check(1, n)) {
			puts("non-boring");
		} else {
			puts("boring");
		}
	}
	return 0;
}