学步园

这道题比赛的时候连读的机会的没有。

但是看了题目表示秒出想法。字符串hash+线段树

关于字符串hash 前几天刚做过一题。就是上上篇博文 《hdu 4821 String》

如果不了解字符串hash可以去看看

http://blog.csdn.net/u010724594/article/details/37819099

与队友共勉。下次记得不要卡题。

---------------------------------------------------------------------------------------

这里重新整理一下字符串hash的段换算公式。

如果我们得到一个长度为k的字符串的hash值 和 该字符串长度为j的前缀hash值

那么该字符串尾部长度为k-j的字符串hash值就可以计算得到 hash[k]-hash[j]*p[k-j+1];

p为辅助数组。p[i]为seed累乘i遍的结果。如果 不知道seed，那去看看前前篇博文吧，连接开头有。

同理可得：如果知道字符串长度为j的hash值，字符串长度为k的hash值。那么他们凭借起来的新字符串s = s1(长度为j)+s2(长度为k)；长度为j+k的hash值可计算：

hash[j+k]=hash[j]*p[k]+hash[k];

这样字符串构造成线段树后，只要知道所有叶子节点的hash值，就可以通过计算得到所有父亲节点的hash值。而单个字母的hash值就是其本身。

这样我们维护两个线段树。一个是从左到右计算hash值另一个是从右到左计算hash值。查询的时候判断下两个字段的hash是否相等就能判断是否为回文串了。

代码如下：

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<iostream>
using namespace std;

typedef long long LL;
const int MAX = 1e5+10;
const int seed = 1331;
const LL MOD = 1e9+7;//虽然用了long long 但还是怕溢出


LL pl[MAX<<2] , pr[MAX<<2] , p[MAX];
char str[MAX];

void build( int l , int r , int id ){
    if( l == r ){
        pl[id] = pr[id] = str[l]-'a';
        return ;
    }
    int m = (l+r)>>1;
    build( l , m , id<<1);
    build( m+1 , r , id<<1|1);
    //pushUp(id);
    pl[id] = (pl[id<<1]*p[r-m]+pl[id<<1|1])%MOD;//从左到右计算
    pr[id] = (pr[id<<1]+pr[id<<1|1]*p[m-l+1])%MOD;//从右到左计算
}
void upDate( int i , char x , int l , int r , int id ){
    if( l == r ){
        pl[id] = pr[id] = x-'a';
        return ;
    }
    int m = ( l+r )>>1;
    if( i<= m ) upDate(i,x,l,m,id<<1);
    else upDate(i,x,m+1,r,id<<1|1);
    pl[id] = (pl[id<<1]*p[r-m]+pl[id<<1|1])%MOD;
    pr[id] = (pr[id<<1]+pr[id<<1|1]*p[m-l+1])%MOD;
}
LL query_l( int L , int R , int l , int r , int id ){
    if( L == l && r == R ){
        return pl[id];
    }
    LL ret = 0;
    int m = ( l+r ) >>1 ;
    if( R <= m ) ret = query_l(L,R,l,m,id<<1);
    else if( L > m ) ret = query_l(L,R,m+1,r,id<<1|1);
    else ret = query_l(L,m,l,m,id<<1)*p[R-m]%MOD+query_l(m+1,R,m+1,r,id<<1|1);
    return ret%MOD;
}
LL query_r( int L , int R , int l , int r , int id ){
    if( L <= l && r <= R ){
        return pr[id];
    }
     LL ret = 0;
    int m = ( l+r ) >>1 ;
    if( R <= m ) ret = query_r(L,R,l,m,id<<1);
    else if( L > m ) ret = query_r(L,R,m+1,r,id<<1|1);
    else ret = query_r(L,m,l,m,id<<1)+query_r(m+1,R,m+1,r,id<<1|1)*p[m-L+1]%MOD;
    return ret%MOD;
}

int main(){
    p[0] = 1;
    for(int i = 1 ; i <MAX; i ++ )
        p[i]=p[i-1]*seed%MOD;
    while(~scanf("%s" , str )){
        int len = strlen(str);
        int n;scanf("%d",&n);
        build(0,len-1,1);
        while(n--){
            char command[100];scanf("%s",command);
            if( strcmp(command , "palindrome?") == 0 ){
                int L , R;scanf("%d%d",&L,&R);
                LL ret1 = query_l(L-1,R-1,0,len-1,1), ret2 = query_r(L-1,R-1,0,len-1,1);
                //cout<<ret1<<" "<<ret2<<endl;
                puts(ret1==ret2?"Yes":"No");
            }else{
                char x[2] ;
                int i ;
                scanf("%d%s" , &i,x);
                upDate(i-1,x[0],0,len-1,1);
            }
        }
    }
    return 0;
}