URAL 1989 Subpalindromes(多項式ハッシュ+セグメントツリー)
URAL 1989 Subpalindromes(多項式ハッシュ+セグメントツリー)
題意:長さ10^5の文字列を与え、m個の操作m<=10^4がある.2つの操作があり,1,[l,r]区間のサブストリングに返信するかどうかを尋ねる,2,i番目の文字をcに変更する.
解題構想:多項式ハッシュを用いると,文列を返すか否かを判断するには,正逆区間のハッシュ値の和が等しいか,すなわちセグメントツリー区間の和を求めるだけで,修正は単点更新である.
題意:長さ10^5の文字列を与え、m個の操作m<=10^4がある.2つの操作があり,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
*/