正解是双哈希，不过一次哈希也能解决。。
然后某个数字就对应一个字符串，虽然有些不同串对应同一个数字，但是概率非常小，可以忽略不计。从左到右、从右到左进行两次hash，如果是回文串，那么对应的整数必定存在某种关系（可以理解成相等），对于更新操作，就是单点更新。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #include<algorithm> #define ll unsigned long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 100005 char s[maxn]; ll F[maxn+1]; int len; struct node{ ll suml,sumr; }tree[maxn<<2];//区间保存从左到右和从右到左的hash值 inline void pushup(int rt){ tree[rt].suml=tree[rt<<1].suml+tree[rt<<1|1].suml; tree[rt].sumr=tree[rt<<1].sumr+tree[rt<<1|1].sumr; } void build(int l,int r,int rt){ if(l==r){ tree[rt].suml=F[l-1]*(s[l-1]-'a'); tree[rt].sumr=F[len-l]*(s[l-1]-'a'); return; } int m=l+r>>1; build(lson); build(rson); pushup(rt); } void update(int pos,int val,int l,int r,int rt){//单点更新 if(l==r){ tree[rt].suml=F[l-1]*val; tree[rt].sumr=F[len-l]*val; return; } int m=l+r>>1; if(pos<=m) update(pos,val,lson); else update(pos,val,rson); pushup(rt); } ll suml,sumr; void query(int x,int y,int l,int r,int rt){ if(x<=l && y>=r){ suml+=tree[rt].suml; sumr+=tree[rt].sumr; return; } int m=l+r>>1; if(x<=m) query(x,y,lson); if(y>m) query(x,y,rson); } int main(){ F[0]=1; for(int i=1;i<=maxn;i++) F[i]=F[i-1]*27;//打表处理 int q; while(scanf("%s",s)!=EOF){ scanf("%d",&q); len=strlen(s); build(1,len,1); char op[20]; int x,y; while(q--){ scanf("%s",op); if(op[0]=='p'){//查询 scanf("%d%d",&x,&y); suml=sumr=0; query(x,y,1,len,1); int k1=x-1;//左到右的长度 int k2=len-y;//右到左的区间长度 if(k1>k2) sumr*=F[k1-k2]; else suml*=F[k2-k1]; cout<<suml<<" "<<sumr<<endl; if(suml==sumr) puts("YES"); else puts("NO"); } else {//单点修改 int x; char tmp[2]; scanf("%d%s",&x,tmp); update(x,tmp[0]-'a',1,len,1); } } } return 0; }