题目大意：给一行字符串，两种操作：change(pos,char)，将pos处字符改为char；isPalindrome(i,j)，询问[i,j]之间是否为回文字符串。
题目分析：做正反两次字符串哈希，如果哈希值一样则回文。用线段树维护哈希值，单点更新即可。
我的挫代码如下：
# include<cstdio>
# include<iostream>
# include<cstring>
# include<algorithm>
using namespace std;
# define mid (l+(r-l)/2) const int N=100000; int seed[2]={31,131};
unsigned int base[2][N+5]; char str[N+5];
char op[2];
unsigned int tr_left[2][N*4+5];
unsigned int tr_right[2][N*4+5]; struct Node{
unsigned int left[2];
unsigned int right[2];
}; inline void init()
{
for(int i=0;i<2;++i){
base[i][0]=1;
for(int j=1;j<=N;++j){
base[i][j]=base[i][j-1]*seed[i];
}
}
} inline void read(int &x)
{
x=0;
char c;
while((c=getchar())&&(c<'0'||c>'9'));
x=c-'0';
while(c=getchar()){
if(c<'0'||c>'9') break;
x=x*10+c-'0';
}
} inline bool ok(Node *a)
{
for(int i=0;i<2;++i)
if(a->left[i]!=a->right[i]) return false;
return true;
} inline void pushUp(int rt,int l,int r)
{
for(int i=0;i<2;++i){
tr_left[i][rt]=tr_left[i][rt<<1]*base[i][r-mid]+tr_left[i][rt<<1|1];
tr_right[i][rt]=tr_right[i][rt<<1|1]*base[i][mid-l+1]+tr_right[i][rt<<1];
}
} inline void build(int rt,int l,int r)
{
if(l==r){
for(int i=0;i<2;++i)
tr_left[i][rt]=tr_right[i][rt]=str[l]-'a'+1;
}else{
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushUp(rt,l,r);
}
} inline void update(int rt,int l,int r,int x,char c)
{
if(l==r){
for(int i=0;i<2;++i)
tr_left[i][rt]=tr_right[i][rt]=c-'a'+1;
}else{
if(x<=mid) update(rt<<1,l,mid,x,c);
else update(rt<<1|1,mid+1,r,x,c);
pushUp(rt,l,r);
}
} inline Node* query(int rt,int l,int r,int L,int R)
{
Node* nde=new Node;
if(L<=l&&r<=R){
for(int i=0;i<2;++i){
nde->left[i]=tr_left[i][rt];
nde->right[i]=tr_right[i][rt];
}
}else{
Node* nde1=NULL;
Node* nde2=NULL;
if(L<=mid) nde1=query(rt<<1,l,mid,L,min(R,mid));
if(R>mid) nde2=query(rt<<1|1,mid+1,r,max(mid+1,L),R);
if(nde1!=NULL&&nde2!=NULL){
for(int i=0;i<2;++i){
nde->left[i]=nde1->left[i]*base[i][R-mid]+nde2->left[i];
nde->right[i]=nde2->right[i]*base[i][mid-L+1]+nde1->right[i];
}
}else{
if(nde1!=NULL){
for(int i=0;i<2;++i){
nde->left[i]=nde1->left[i];
nde->right[i]=nde1->right[i];
}
}else if(nde2!=NULL){
for(int i=0;i<2;++i){
nde->left[i]=nde2->left[i];
nde->right[i]=nde2->right[i];
}
}
}
if(nde1!=NULL) delete nde1;
if(nde2!=NULL) delete nde2;
}
return nde;
} int main()
{
init();
int m;
while(~scanf("%s",str))
{
int n=strlen(str);
build(1,0,n-1);
scanf("%d",&m);
int a,b;
char ch[2];
while(m--)
{
scanf("%s",op);
if(op[0]=='p'){
read(a);
read(b);
Node *nde=query(1,0,n-1,a-1,b-1);
if(ok(nde)) printf("Yes\n");
else printf("No\n");
delete nde;
}else if(op[0]=='c'){
read(a);
scanf("%s",ch);
update(1,0,n-1,a-1,ch[0]);
}
}
}
return 0;
}