思路
判断一个字符串是否是回文串，可以从它的本质出发：正着读和倒着读是一样的。快速判断它正着和反着是否一样，用字符串哈希即可。又因为涉及单点修改，区间查询，那么使用线段树维护这两个值就行了。
这里讲一下如何 pushup。以正着的哈希值为例：我们要更新 \(p\) 这个点的 \(hash\) 值，已知 \(p\) 的左右儿子的哈希值 \(ls_{hash}\) 和 \(rs_{hash}\)，那么按照正常的 \(hash\) 值更新右边的一坨式子应该要乘上一些 \(base\)，乘多少呢？因为我们是以左边为起点，当更新到 \(rs\) 的左端点时左边已经乘了 \(ls.r-ls.l\) 个 \(base\)，\(rs\) 的左端点就应该乘上 \(ls.r-ls.l+1\) 个 \(base\)。而 \(rs\) 内部的值是已经算好了的，所以整体乘上 \(ls.r-ls.l+1\) 个 \(base\) 就好了。也就是 \(base^{ls.r-ls.l+1}\)。
此题也就没什么难度了。小清新线段树。
code
#include<bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
int n,q;
const int mod=998244353;
const ll base=47;
ll pw[1000005];
char s[1000005];
struct Tree{
int l,r;
ll lnum,rnum;
}tr[4000005];
void pushup(int p){
tr[p].lnum=(tr[ls].lnum+(pw[tr[ls].r-tr[ls].l+1]*tr[rs].lnum)%mod)%mod;//更新hash值
tr[p].rnum=(tr[rs].rnum+(pw[tr[rs].r-tr[rs].l+1]*tr[ls].rnum)%mod)%mod;
}
void build(int p,int l,int r){
tr[p].l=l;tr[p].r=r;
if(l==r){
tr[p].lnum=tr[p].rnum=(ll)(s[l]-'a'+1);
return;
}
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void update(int p,int x,char c){
if(tr[p].l==tr[p].r){
tr[p].lnum=tr[p].rnum=(ll)(c-'a'+1);
return;
}
int mid=tr[p].l+tr[p].r>>1;
if(x<=mid)update(ls,x,c);
else update(rs,x,c);
pushup(p);
}
Tree query(int p,int l,int r){
if(tr[p].l>=l&&tr[p].r<=r)return tr[p];
int mid=tr[p].l+tr[p].r>>1;
if(r<=mid)return query(ls,l,r);
if(l>mid)return query(rs,l,r);
Tree ld=query(ls,l,r),rd=query(rs,l,r);//合并两段的hash值
Tree res;
res.l=ld.l;res.r=rd.r;
res.lnum=(ld.lnum+(pw[ld.r-ld.l+1]*rd.lnum)%mod)%mod;
res.rnum=(rd.rnum+(pw[rd.r-rd.l+1]*ld.rnum)%mod)%mod;
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q;
cin>>(s+1);
pw[0]=1;
for(int i=1;i<=n;++i)pw[i]=(pw[i-1]*base)%mod;//预处理base的次幂
build(1,1,n);
while(q--){
int op,l,r,x;
char c;
cin>>op;
if(op==1){
cin>>x>>c;
update(1,x,c);
}
else{
cin>>l>>r;
Tree now=query(1,l,r);
if(now.lnum==now.rnum)cout<<"Yes\n";//正着读倒着读相同
else cout<<"No\n";
}
}
return 0;
}