BZOJ-1293: [SCOI2009]生日礼物（离散化+单调

题目：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 ;
}