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

#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 
*/