URAL 1989 Subpalindromes (多项式hash) +【线段树】

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

<题目链接>

<转载于 >>> >

题目大意：
给你一段字符串，进行两种操作：
1.询问[l,r]这个区间中的字符串是否是回文串；

2.更改该字符串中对应下标的字符。

解题分析：

快速判断字符串是不是回文串，可以用到多项式Hash。假设一个串s，那么字串s[i, j]的Hash值就是H[i, j]=s[i]+s[i+1]*x+s[i+2]*(x^2)+...+s[j]*(x^(j-i))。由于只有小写字母，因此x取27。但是H[i, j]这会很大，我们取模就可了，可以把变量类型设为unsigned long long, 那么自动溢出就相当于模2^64了。对于不同串但是Hash相同的情况，这种情况的概率是非常小的，通常可以忽略，当然我们也可以对x取多次值，求出不同情况下的Hash值。然后我们就可以用线段树或者树状数组来维护这个和了，复杂度O(nlogn)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define Lson rt<<1,l,mid
#define Rson rt<<1|1,mid+1,r
#define N 100005
#define ull unsigned long long
ull f[N];
char s[N];
int n;
struct Tree{
ull lsum,rsum; //左->右和右->左的hash值
}tr[N<<];
void Pushup(int rt){ //将该区间内从左到右和从右到左的多项式hash的每一位相加
tr[rt].lsum=tr[rt<<].lsum+tr[rt<<|].lsum;
tr[rt].rsum=tr[rt<<].rsum+tr[rt<<|].rsum;
}
void build(int rt,int l,int r){
if(l==r){
tr[rt].lsum=f[l-]*(s[l-]-'a'); //得到hash多项式相应位置的hash值
tr[rt].rsum=f[n-l]*(s[l-]-'a');
return;
}
int mid=(l+r)>>;
build(Lson);
build(Rson);
Pushup(rt);
}
void update(int rt,int l,int r,int pos,int num){
if(l==r){
tr[rt].lsum=f[l-]*num;
tr[rt].rsum=f[n-l]*num;
return;
}
int mid=(l+r)>>;
if(pos<=mid)update(Lson,pos,num);
if(pos>mid)update(Rson,pos,num);
Pushup(rt);
}
ull lsum,rsum;
void query(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R){
lsum+=tr[rt].lsum;
rsum+=tr[rt].rsum;
return;
}
int mid=(l+r)>>;
if(L<=mid)query(Lson,L,R);
if(R>mid)query(Rson,L,R);
}
int main(){
f[]=;
for(int i=;i<N;i++)
f[i]=f[i-]*; //预处理27的1~N次方
while(scanf("%s",s)!=EOF){
n=strlen(s);
build(,,n);
int q;scanf("%d",&q);
while(q--){
scanf("%s",s);
if(s[]=='p'){
int x,y;scanf("%d%d",&x,&y);
lsum=rsum=;
query(,,n,x,y);
int k1=x-;
int k2=n-y;
if(k1>k2)rsum*=f[k1-k2]; //按照上面的计算方式，从左向右和从右向左的相同hash多项式的计算中，短区域中的每一项会比长区域少乘f[k1-k2](或f[k2-k1])次方,所以这里要讲相差的f[]乘上，再进行比较
else lsum*=f[k2-k1];
if(lsum==rsum)printf("Yes\n");
else printf("No\n");
}
else{
int x;
scanf("%d%s",&x,s);
update(,,n,x,s[]-'a');
}
}
}
}