题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1989
题目大意：

给你一个字符串s, q个操作：

1：palindrome? x y  :询问[x, y]是否为回文串
2：change 4 b       :把s[4]修改为b


我们来梳理一下字符串的子串的求法：

以左为高位：
1：前缀和

ull Hash(char s[])
{
    int len=strlen(s);
    ull ans=0;

    g[0]=s[0];
    for(int i=1;i<len;i++)
    {
        g[i]=g[i-1]*base+s[i];
    }
    return g[len-1];
}

void getp()
{
    p[0]=1;
    for(int i=1;i<=maxn;i++)
    {
        p[i]=p[i-1]*base;
    }
}

[L, R] = 

ull getLR(int l, int r)//取出T里l - r里面的字符串的hash值
{
    return g[r]-g[l-1]*p[r-l+1];
}

假如对于：123456 base=10

那么： g[1]=1
	  g[2]=12
	  g[3]=123
	  g[4]=1234
	  g[5]=12345
	  g[6]=123456
	  
求[2, 3]：
	  g[3]-g[1]*p[3](base^2)
	 =123-1*100
	 =23
我们可以看到这种方法是对的。但是这个方法每次修改后必须把修改位及其以后位的哈希值
要重新计算。无法用线段树维护。

2：位权法：以右为高位

ull Hash(char s[])
{
    int len=strlen(s);
    ull ans=0;

    g[0]=s[0];
    for(int i=1;i<len;i++)
    {
        g[i]=s[i]*p[i];
    }
    
    return g[len-1];
}

假如对于：123456 base=10

那么： g[1]=1
	  g[2]=20
	  g[3]=300
	  g[4]=4000
	  g[5]=50000
	  g[6]=600000
	  
求[2, 3]：
	  g[2]+g[3]
	 =20+300
	 =320
这个时候还不是哈希值，因为长度为2，哈希值最大为99，我们必须让他们最低位的位权变为1
g[L]+....+g[R]/(p[L-1]);

320/10=32。因为是以右为高位(方便维护),如果以左位高位应该就是：23。

哈希值用23或者32表示这个子串效果是一样的。

所以这个发现每次修改，只修改那一位就可以了，方便用线段树/数状数组维护。

3.区间修改：以右为高位

如果说把[L, R]的区间修改成某个字符，怎么用线段树区间修改来维护。
我们先看线段树怎么维护字符串哈希：




这个时候也可以满足单点修改，递归维护就可以了。

如果我们把[2, 3]区间全部修改为5,那么应该怎么维护：

我们先看看一个区间的哈希是怎么求的：
假如区间长度为Len
那么这个区间的的哈希值为
sum[i]=a[1]*p[0] + a[2]*p[1] + a[3]*p[2] + a[4]*p[3] +....+ a[Len]*p[Len-1]

因为这个区间的所有值都修改为x。
那么合并同类项：
sum[i]=x*(p[0]+p[1]+.....+p[Len-1])
把p[i]的前缀和维护一下sf[i]，那么sum[i]=x*sf[Len-1];

所以这样就维护出来了。

这道题，让我们修改并且重新是否为回文串。

假如区间[L, R]的中间长度（不包含s[L], s[R]）为Len


if(s[L, Len/2]==strrev（s[Len/2+1， R])）//strrev为倒序
{
	//回文串
}


因为哈希不能维护倒序。但是我们可以开两个数状数组，一个维护[1, n]， 另外一个维护[n, 1]就
行了，查询倒序只要查询另一个数状数组就行了。

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull base =27;

int Len, x, n;
ull sum[2][100005]={0};
char s[100005];
ull p[100005];

void add(int p, ull y, int k)
{
    if(k==0)
    {
        while(p<=Len)
        {
            sum[0][p]+=y;
            p+=(p&-p);
        }
    }
    else
    {
        while(p<=Len)
        {
            sum[1][p]+=y;
            p+=(p&-p);
        }
    }
}

ull cx(int p, int k)
{
    ull ans=0;

    if(k==0)
    {
        while(p)
        {
            ans+=sum[0][p];
            p-=(p&-p);
        }
    }
    else
    {
        while(p)
        {
            ans+=sum[1][p];
            p-=(p&-p);
        }
    }

    return ans;
}

ull LR(int L, int R, int k)
{
    return cx(R, k)-cx(L-1, k);
}

void getp()
{
    p[0]=1;
    for(int i=1;i<=100005;i++)
    {
        p[i]=p[i-1]*base;
    }
}

int main()
{
    getp();
    scanf("%s",s+1);
    Len=strlen(s+1);
    for(int i=1;i<=Len;i++)
    {
        add(i, s[i]*p[i-1], 0);
        add(i, s[Len-i+1]*p[i-1], 1);
    }

    scanf("%d",&n);
    char op[20];
    while(n--)
    {
        scanf("%s",&op);
        if(op[0]=='p')
        {
            int x, y;
            scanf("%d%d",&x,&y);
            int d=y-x-1;
            d/=2;
            if(x==y)
            {
                printf("Yes\n");
                continue;
            }
            ull E1=LR(x, d+x, 0);
            ull E2=LR(Len-y+1, Len-y+1+d, 1);
            /******************/把最低位化成相同的位数
            if(x-1>(Len-y))
            {
                E2*=p[x-1-(Len-y)];
            }
            else
            {
                E1*=p[(Len-y)-x+1];
            }
            /******************/
            if(E1==E2)
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }

        }
        else
        {
            int x;
            char k;
            scanf("%d %c",&x,&k);
            /*******************/
            add(x, (k-s[x])*p[x-1], 0);
            add(Len-x+1, (k-s[x])*p[Len-x], 1);
            /*******************/
            s[x]=k;
        }
    }

    return 0;
}