水题一道，用线段树维护哈希值，脑补一下加减乱搞搞……注意细节就过了
一定注意细节……
#include#include #include #include #include #define maxn 100050#define base 163#define left (rt<<1)#define right (rt<<1|1)#define mid ((l+r)>>1)#define lson l,mid,left#define rson mid+1,r,rightusing namespace std;unsigned long long d[maxn*5];unsigned long long w[maxn*5];unsigned long long bs[maxn];char q[maxn];inline int count(char c){ return c-'a'+1; }inline void pushup(int rt,int m){ d[rt]=d[left]*bs[m>>1]+d[right]; w[rt]=w[right]*bs[m-(m>>1)]+w[left];}void build(int l,int r,int rt){ if(l==r){ d[rt]=w[rt]=count(q[l]); return; } build(lson); build(rson); pushup(rt,r-l+1);}unsigned long long queryfro(int from,int to,int l,int r,int rt){ if(from<=l&&to>=r) return d[rt]; unsigned long long ans=0; int len=0; if(to>mid){ len=min(to,r)-mid; ans=queryfro(from,to,rson); } if(from<=mid) ans+=queryfro(from,to,lson)*bs[len]; return ans;}unsigned long long querysub(int from,int to,int l,int r,int rt){ if(from<=l&&to>=r) return w[rt]; unsigned long long ans=0; int len=0; if(from<=mid){ len=mid-max(from,l)+1; ans=querysub(from,to,lson); } if(to>mid) ans+=querysub(from,to,rson)*bs[len]; return ans;}void update(int o,char c,int l,int r,int rt){ if(l==r){ d[rt]=w[rt]=count(c); return; } if(o<=mid) update(o,c,lson); else update(o,c,rson); pushup(rt,r-l+1);}int main(){ scanf("%s",q+1); int n=strlen(q+1),m; scanf("%d",&m); bs[0]=1; for(int i=1;i<=n;++i) bs[i]=bs[i-1]*base; build(1,n,1); for(int i=1;i<=m;++i){ char c[15]; int x,y;char o[10]; scanf("%s%d",c,&x); if(c[0]=='p'){ scanf("%d",&y); if(queryfro(x,y,1,n,1)==querysub(x,y,1,n,1)) printf("Yes\n"); else printf("No\n"); } else{ scanf("%s",o); update(x,o[0],1,n,1); } } return 0;}/*abcda5palindrome? 1 5palindrome? 1 1change 4 bpalindrome? 1 5palindrome? 2 4*/