题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1293
随便离散化一下，然后单调队列就可以了，单调队列中的位置单调，如果队首踢出去了仍然存在k种颜色，则踢开队首元素，队尾不需要维护。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define inf 0x7fffffff
#define maxn 1000100
#define maxk 101
struct node {
int v , t ;
void oper( int _v , int _t ) {
v = _v , t = _t ;
}
bool operator < ( const node &a ) const {
return t < a.t ;
}
} a[ maxn ] , q[ maxn ] ;
int n , k , cnt[ maxk ] , counter = 0 , m = 0 , head = 1 , tail = 0 , ans = inf ;
int main( ) {
scanf( "%d%d" , &n , &k ) ;
for ( int i = 0 ; i ++ < k ; ) {
int x ; scanf( "%d" , &x ) ;
while ( x -- ) {
int pos ; scanf( "%d" , &pos ) ;
a[ ++ m ].oper( i , pos ) ;
}
}
sort( a + 1 , a + m + 1 ) ;
memset( cnt , 0 , sizeof( cnt ) ) ;
for ( int i = 1 , j ; i <= n ; ) {
for ( j = i ; a[ j + 1 ].t == a[ j ].t && j < n ; ++ j ) ;
for ( int h = i ; h <= j ; ++ h ) {
q[ ++ tail ] = a[ h ] ;
if ( ! ( cnt[ a[ h ].v ] ++ ) ) ++ counter ;
}
for ( ; cnt[ q[ head ].v ] > 1 ; -- cnt[ q[ head ++ ].v ] ) ;
if ( counter == k ) ans = min( ans , a[ i ].t - q[ head ].t ) ;
i = j + 1 ;
}
printf( "%d\n" , ans ) ;
return 0 ;
}
