CFR 580 E. Kefa and Watch ( Hashing + Segment Tree )

Problem - E - Codeforces
Seems like there were cases that deliberately hacked those who used only one MOD value for hashing, where such hack tests can easily be prepared with a little knowledge of birthday paradox.
First, it might be a little tricky to find out that to verdict whether a string S is P-periodic, is essentially equivalent to asking whether S[ 0, S.end() - P ) is identical to S[ P, S.end() ).
Then it is obvious to see that if we could somehow quickly modify a substring and make fast queries on whether two substrings are identical, the confrontation will be settled easily. Fortunately, this can be done with hashing on segment tree. We will have each node store the hash value of the substring where its range maps to. Be wary that when retrieving the number of characters right to the current node, that value should be max( 0, min( qr - mid, rb - mid ) ).

const int SIGMA = 13;
const int MOD[] = { ( int ) 1e9 + 7, ( int ) 1e9 + 9, ( int ) 1e4 + 7, 103, 107 };

const int MAXN = 1e5 + 5;
int pow_mod[ MAXN ][ sizeof( MOD ) / sizeof( int ) ];
int hv_all_one[ MAXN ][ sizeof( MOD ) / sizeof( int ) ];

struct itvt{
    int mod, mod_id;
    int tag;
    int val;
    itvt *lc, *rc;
    itvt( int m_id ){
        mod_id = m_id;
        mod = MOD[ mod_id ];
        tag = -1;
        val = 0;
        lc = rc = NULL;
    }
    void push( int lb, int rb ){
        if( tag != -1 ){
            int mid = lb + rb >> 1;
            lc->tag = tag, lc->val = 1LL * tag * hv_all_one[ mid - lb ][ mod_id ] % mod,
            rc->tag = tag, rc->val = 1LL * tag * hv_all_one[ rb - mid ][ mod_id ] % mod;
            tag = -1;
        }
    }
    void pull( int lb, int rb ){
        int mid = lb + rb >> 1;
        val = ( 1LL * lc->val * pow_mod[ rb - mid ][ mod_id ] % mod + rc->val ) % mod;
    }
    void update( int lb, int rb, int ql, int qr, int v ){
        if( qr <= lb or rb <= ql ) return;
        if( ql <= lb and rb <= qr ){
            tag = v;
            val = 1LL * v * hv_all_one[ rb - lb ][ mod_id ] % mod;
            return;
        }
        push( lb, rb );
        int mid = lb + rb >> 1;
        lc->update( lb, mid, ql, qr, v );
        rc->update( mid, rb, ql, qr, v );
        pull( lb, rb );
    }
    int query( int lb, int rb, int ql, int qr ){
        if( qr <= lb or rb <= ql ) return 0;
        if( ql <= lb and rb <= qr ) return val;
        push( lb, rb );
        int mid = lb + rb >> 1; //                                               !!!!!!!!
        int res = ( 1LL * lc->query( lb, mid, ql, qr ) * pow_mod[ max( 0, min( qr - mid, rb - mid ) ) ][ mod_id ] % mod
                        + rc->query( mid, rb, ql, qr ) ) % mod;
        pull( lb, rb );
        return res;
    }
};

itvt* build_itvt( int lb, int rb, int mod_id, const string &s ){
    itvt *t = new itvt( mod_id );
    if( lb + 1 == rb ){
        t->val = s[ lb ] - '0' + 1;
        return t;
    }
    int mid = lb + rb >> 1;
    t->lc = build_itvt( lb, mid, mod_id, s );
    t->rc = build_itvt( mid, rb, mod_id, s );
    t->pull( lb, rb );
    return t;
}

void solve(){
    for( int i = 0; i < sizeof( MOD ) / sizeof( int ); ++i ){
        pow_mod[ 0 ][ i ] = 1;
        hv_all_one[ 0 ][ i ] = 0;
        for( int j = 0; j + 1 < MAXN; ++j )
            pow_mod[ j + 1 ][ i ] = 1LL * pow_mod[ j ][ i ] * SIGMA % MOD[ i ],
            hv_all_one[ j + 1 ][ i ] = ( 1LL * hv_all_one[ j ][ i ] * SIGMA % MOD[ i ] + 1 ) % MOD[ i ];
    }
    int N, M, K; cin >> N >> M >> K;
    string s; cin >> s;
    vector< itvt* > root( sizeof( MOD ) / sizeof( int ) );
    for( int i = 0; i < sizeof( MOD ) / sizeof( int ); ++i )
        root[ i ] = build_itvt( 0, N, i, s );
    for( int i = 0; i < M + K; ++i ){
        int op; cin >> op;
        if( op == 1 ){
            int ql, qr, c; cin >> ql >> qr >> c;
            --ql; // [ ql + 1, qr + 1 ] -> [ ql, qr + 1 )
            for( int i = 0; i < sizeof( MOD ) / sizeof( int ); ++i )
                root[ i ]->update( 0, N, ql, qr, c + 1 );
        } else{
            int ql, qr, d; cin >> ql >> qr >> d;
            --ql;
            int ng = 0;
            for( int i = 0; i < sizeof( MOD ) / sizeof( int ); ++i )
                if( root[ i ]->query( 0, N, ql, qr - d )
                 != root[ i ]->query( 0, N, ql + d, qr ) )
                    ng = 1;
            if( ng ) cout << "NO\n";
            else cout << "YES\n";
        }
    }
}

int main(){
    ios::sync_with_stdio( false );
    solve();
    return 0;
}