学步园

URAL 1989 Subpalindromes(多项式哈希+线段树)

题意：给出一个字符串，长度为10^5，有m个操作m<= 10 ^ 4。有两种操作，1,询问[l,r]区间的子串是否回文，2，将第i个字符改为c。

解题思路：用多项式哈希，那么我们判断是否回文串，就只要看正反区间的哈希值之和是否相等了，也就是线段树区间求和，那么修改就是单点更新了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define ull __int64
#include<iostream>
using namespace std ;

const int maxn = 111111 ;
const int x = 123 ;
ull sum[2][maxn<<2] ;
ull h[maxn] , p[maxn] ;
char s[maxn] ;

inline void push_up ( int rt , int flag ) {
    sum[flag][rt] = sum[flag][rt<<1] + sum[flag][rt<<1|1] ;
}

void build ( int l , int r , int rt , int flag ) {
    sum[flag][rt] = 0 ;
    if ( l == r ) {
        sum[flag][rt] = h[l] ;
        return ;
    }
    int m = ( l + r ) >> 1 ;
    build ( lson , flag ) ;
    build ( rson , flag ) ;
    push_up ( rt , flag ) ;
}

void update ( int a , ull b , int l , int r , int rt , int flag ) {
    if ( l == r ) {
        sum[flag][rt] = b ;
        return ;
    }
    int m = ( l + r ) >> 1 ;
    if ( a <= m ) update ( a , b , lson , flag ) ;
    else update ( a , b , rson , flag ) ;
    push_up ( rt , flag ) ;
}

ull query ( int a , int b , int l , int r , int rt , int flag ) {
    if ( a <= l && r <= b ) return sum[flag][rt] ;
    int m = ( l + r ) >> 1 ;
    ull ret = 0 ;
    if ( a <= m ) ret = query ( a , b , lson , flag ) ;
    if ( m < b ) ret += query ( a , b , rson , flag ) ;
    return ret ;
}

int main () {
    int i , j , k , m , a , b , c , d ;
    char op[111] ;
    while ( scanf ( "%s" , s ) != EOF ) {
        scanf ( "%d" , &m ) ;
        int len = strlen ( s ) ;
        p[0] = 1 ;
        for ( i = 1 ; i <= len ; i ++ ) p[i] = p[i-1] * x ;
        for ( i = 0 ; i < len ; i ++ )
            h[i+1] = p[i] * (ull) s[i] ;
        int n = len ;
        build ( 1 , n , 1 , 0 ) ;
        reverse ( s , s + len ) ;
        for ( i = 0 ; i < len ; i ++ )
            h[i+1] = p[i] * (ull) s[i] ;
        build ( 1 , n , 1 , 1 ) ;
        while ( m -- ) {
            scanf ( "%s" , op ) ;
            if ( op[0] == 'p' ) {
                scanf ( "%d%d" , &a , &b ) ;
                ull k1 = query ( a , b , 1 , n , 1 , 0 ) ;
                int l = len - b + 1 , r = len - a + 1 ;
                ull k2 = query ( l , r , 1 , n , 1 , 1 ) ;
                int t1 = a - 1 , t2 = len - b ;
                if ( t2 > t1 ) k1 *= p[t2-t1] ;
                else k2 *= p[t1-t2] ;
                if ( k1 == k2 ) puts ( "Yes" ) ;
                else puts ( "No" ) ;
            }
            else {
                scanf ( "%d%s" , &a , op ) ;
                update ( a , (ull) p[a-1] * op[0] , 1 , n , 1 , 0 ) ;
                update ( len - a + 1 , (ull) p[len-a] * op[0] , 1 , n , 1 , 1 ) ;
                ull k1 , k2 ;
            }
        }
    }
    return 0 ;
}
/*
ab
100
c 1 b
*/