原题:

一个序列被称为是不无聊的，当且仅当它的每个子串存在一个独一无二的数字，即每个子串里至少存在一个数字只出现一次.给定一个整数序列，请你判断它是不是不无聊的.

思路：

从1到n枚举r,设fi表示区间[i,r]中仅出现一次的数的个数，考虑r到r+1的变化若r+1还未出现过，则[1,r]都加1.否则记上次出现时的下标为j,上上次出现时的下标为k则fj+1~fr+1都加1,fk+1~fj,都减1序列的合法条件即为任意时刻 的值均大于零.

代码:

#include<cstdio>
#include<algorithm>
using namespace std;

char ch;
bool k;
int pre[200005],chaf[200005],in[200005],n,sum;

void read(int &kk) {
	kk = 0;
	ch = getchar();
	while(ch < '0' or ch > '9') ch = getchar();
	while(ch >= '0' or ch >= '9') kk = kk*10+(ch-'0'),ch = getchar();
}

void add(int l,int r,int num) {
	chaf[l] += num;
	chaf[r+1] -= num;
}



void solve() {
	read(n);
	int cnt[200005];
	for(int i = 1; i <= n; i++) {
		read(in[i]);
		if(!cnt[in[i]])pre[i] = 0;
		else pre[i] = cnt[in[i]] ;
		cnt[in[i]] = i;
	}
	for(int i = 1; i <= n; i++) {
		if(pre[i] == 0) add(1,i,1);
		else  add(pre[i]+1,i,1), add(pre[pre[i]]+1,pre[i],-1);
		sum = 0;
		for(int j = 1; j <= i; j++) {
			sum += chaf[j];
			printf("%d ",sum);
			if(sum < 0)//<0 与<=0会影响上面sum的输出
			{
				printf("boring\n");
				return ;
			}
				
		}
	}
	printf("non-boring\n");
	for(int i = 1; i <= n; i++)
		pre[i] = chaf[i] = cnt[i] = in[i] = 0;
}

int main() {
	int t;
	read(t);
	while(t--) {
		solve();
	}
}

数据点:

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

输出:

non-boring
boring
non-boring
boring

问题:

见注释