[ABC331F] Palindrome Query 题解

思路

判断一个字符串是否是回文串，可以从它的本质出发：正着读和倒着读是一样的。快速判断它正着和反着是否一样，用字符串哈希即可。又因为涉及单点修改，区间查询，那么使用线段树维护这两个值就行了。

这里讲一下如何 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;
}