BZOJ 4059: [Cerc2012]Non-boring sequences ( )

要快速在一段子序列中判断一个元素是否只出现一次 , 我们可以预处理出每个元素左边和右边最近的相同元素的位置 , 这样就可以 O( 1 ) 判断.

考虑一段序列 [ l , r ] , 假如我们找到了序列中唯一元素的位置 p , 那我们只需检查 [ l , p - 1 ] & [ p + 1 , r ] 是否 non-boring 即可 . 

如何检查 序列 [ l , r ] 呢 ? 假如从左往右或者从右往左找 , 最坏情况下是 O( n ) , 总时间复杂度会变成 O( n² ) ; 假如我们从两边往中间找 , 那最坏情况是唯一元素在中间 ,  单次是 O( n ) , 但是现在划分出来的递归处理的左右两部分都是原序列长度的一半 , 这样总时间复杂度就是 O( nlogn ) 了

------------------------------------------------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<map>

#define rep( i , n ) for( int i = 0 ; i < n ; ++i )

#define clr( x , c ) memset( x , c , sizeof( x ) )

using namespace std;

const int maxn = 200000 + 5;

int seq[ maxn ] , L[ maxn ] , R[ maxn ] , n;

map< int , int > S;

#define UNIQUE( x ) ( L[ x ] < l && R[ x ] > r )

bool check( int l , int r ) {

if( l >= r ) return true;

int t[ 2 ] = { l , r };

for( int p = 0 ; t[ 0 ] <= t[ 1 ] ; ( p ^= 1 ) ? t[ 0 ]++ : t[ 1 ]-- )

if( UNIQUE( t[ p ] ) )

   return check( l , t[ p ] - 1  ) && check( t[ p ] + 1 , r );

return false;

}

int main() {

freopen( "test.in" , "r" , stdin );

int t;

cin >> t;

while( t-- ) {

scanf( "%d" , &n );

rep( i , n )

L[ i ] = -1 , R[ i ] = n;

S.clear();

rep( i , n ) {

   scanf( "%d" , seq + i );

   if( S.find( seq[ i ] ) != S.end() )

       L[ i ] = S[ seq[ i ] ];

   S[ seq[ i ] ] = i;

}

S.clear();

for( int i = n - 1 ; i >= 0 ; i-- ) {

   if( S.find( seq[ i ] ) != S.end() )

R[ i ] = S[ seq[ i ] ];

   S[ seq[ i ] ] = i;

}

printf( check( 0 , n - 1 ) ? "non-boring\n" : "boring\n" );

}

return 0;

}

------------------------------------------------------------------------------------------------------

4059: [Cerc2012]Non-boring sequences

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 300  Solved: 105
[Submit][Status][Discuss]

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

HINT

Source

鸣谢Tjz