BZOJ-3207: 花神的嘲讽计划Ⅰ（字符串HASH+主席树）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3207

明显用HASH维护就可以了。。。为了保险取了13和29两个进制。。。然后主席树维护即可。。（我偷懒，写了线段树套multiset，刚好10s卡过去了，就不改了。。。其实也可以整体二分来着。。。）

代码（sgt+multiset）：

30adcbef76094b3662698b88a1cc7cd98c109dd8.jpg.png

#include <cstdio>

#include <algorithm>
#include <cstring>
#include <set>
 
using namespace std ;
 
#define ULL unsigned long long
#define MAXN 150000
#define MAXK 25
#define check( ch ) ( ch >= '0' && ch <= '9' )
 
void getint( ULL &t ) {
    bool flag = false ;
    int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) if ( ch == '-' ) flag = true ;
    t = ch - '0' ;
    for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) t *= 10 , t += ch - '0' ;
    if ( flag ) t = - t ;
}
 
struct type {
    int h0 , h1 ;
    bool operator < ( const type &a ) const {
        return ( h0 < a.h0 ) || ( h0 == a.h0 && h1 < a.h1 ) ;
    }
    bool operator == ( const type &a ) const {
        return h0 == a.h0 && h1 == a.h1 ;
    }
    bool operator > ( const type &a ) const {
        return ( h0 > a.h0 ) || ( h0 == a.h0 && h1 > a.h1 ) ;
    }
} w[ MAXN ] ;
 
ULL a[ MAXN ] , H[ MAXN ][ MAXK ][ 2 ] , E0[ MAXK ] , E1[ MAXK ] ;
 
int n , m , k ;
 
multiset < type > S[ MAXN * 4 ] ;
 
void Build( int l , int r , int t ) {
    S[ t ].clear(  ) ;
    for ( int i = l ; i <= r ; i ++ ) S[ t ].insert( w[ i ] ) ;
    if ( l == r ) return ;
    int mid = ( l + r ) >> 1 ;
    Build( l , mid , t << 1 ) , Build( mid + 1 , r , ( t << 1 ) ^ 1 ) ;
}
 
bool query( int l , int r , int L , int R , type k , int t ) {
    if ( l == L && r == R ) {
        return S[ t ].find( k ) != S[ t ].end(  ) ;
    }
    int mid = ( L + R ) >> 1 ;
    if ( r <= mid ) return query( l , r , L , mid , k , t << 1 ) ;
    if ( l > mid ) return query( l , r , mid + 1 , R , k , ( t << 1 ) ^ 1 ) ;
    return query( l , mid , L , mid , k , t << 1 ) || query( mid + 1 , r , mid + 1 , R , k , ( t << 1 ) ^ 1 ) ;
}
 
type Hash( ULL *u ) {
    type ret ;
    ret.h0 = ret.h1 = 0 ;
    for ( int i = 0 ; i ++ < k ; ) {
        ret.h0 *= 13 , ret.h1 *= 29 ;
        ret.h0 += u[ i ] , ret.h1 += u[ i ] ;
    }
    return ret ;
}
 
ULL u[ MAXK ] ;
 
int main(  ) {
    E0[ 0 ] = E1[ 0 ] = 1 ;
    for ( int i = 0 ; i ++ < MAXK - 1 ; ) E0[ i ] = E0[ i - 1 ] * 13 , E1[ i ] = E1[ i - 1 ] * 29 ;
    scanf( "%d%d%d" , &n , &m , &k ) ;
    for ( int i = 0 ; i ++ < n ; ) {
        getint( a[ i ] ) ;
        H[ i ][ 0 ][ 0 ] = H[ i ][ 0 ][ 1 ] = 0 ;
    }
    for ( int i = 0 ; i ++ < k ; ) {
        for ( int j = 0 ; j ++ < n ; ) {
            H[ j ][ i ][ 0 ] = H[ j ][ i - 1 ][ 0 ] * 13 + a[ j + i - 1 ] ;
            H[ j ][ i ][ 1 ] = H[ j ][ i - 1 ][ 1 ] * 29 + a[ j + i - 1 ] ;
        }
    }
    for ( int i = 0 ; i ++ < n - k + 1 ; ) w[ i ].h0 = H[ i ][ k ][ 0 ] , w[ i ].h1 = H[ i ][ k ][ 1 ] ;
    Build( 1 , n - k + 1 , 1 ) ;
    while ( m -- ) {
        int l , r ; scanf( "%d%d" , &l , &r ) ;
        for ( int i = 0 ; i ++ < k ; ) getint( u[ i ] ) ;
        if ( r - l + 1 < k ) printf( "No\n" ) ; else {
            printf( query( l , r - k + 1 ,1 , n - k + 1 , Hash( u ) , 1 ) ? "No\n" : "Yes\n" ) ;
        }
    }
    return 0 ;
}