首页 > 代码库 > AC dreamoj 1011 树状数组+hash维护字符串的前缀和
AC dreamoj 1011 树状数组+hash维护字符串的前缀和
http://acdream.info/problem?pid=1019
Problem Description
Now we have a long long string, and we will have two kinds of operation on it.
C i y : change the ith letter to y.
Q i j : check whether the substring from ith letter to jth letter is a palindrome.
Input
There are multiple test cases.
The first line contains a string whose length is not large than 1,000,000.
The next line contains a integer N indicating the number of operations.
The next N lines each lines contains a operation.
All letters in the input are lower-case.
Output
For each query operation, output "yes" if the corresponding substring is a palindrome, otherwise output "no".
Sample Input
aaaaa 4 Q 1 5 C 2 b Q 1 5 Q 1 3
Sample Output
yes no yes
/** ACdreamoj 1019 树状数组+hash维护字符串的前缀和 题目大意: 给定一个字符串,单点更新,区间查询该区间是不是回文串。 解题思路: hash是x1 * p^1+ x2*p^2 +x3*p^3...可以用树状数组维护前缀和, 维护两个串,一个是正串,另一个是反串用于比较。 字符串区间s[l~r]的哈希值为sum(s[r]-s[l-1])/Hash[l-1]; */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; typedef unsigned long long LL; const int maxn=1000010; const int seed=13; LL Hash[maxn],C[2][maxn]; char s[maxn]; int len; void init() { Hash[0]=1; for(int i=1;i<maxn;i++) Hash[i]=Hash[i-1]*seed; } int lowbit(int x) { return x&(-x); } void add(int i,int x,LL pos) { while(x<=len) { C[i][x]+=pos; x+=lowbit(x); } } LL sum(int i,int x) { LL ans=0; while(x) { ans+=C[i][x]; x-=lowbit(x); } return ans; } LL gethash(int i,int l,int r) { return sum(i,r)-sum(i,l-1); } int main() { init(); while(~scanf("%s",s+1)) { memset(C,0,sizeof(C)); len=strlen(s+1); for(int i=1;i<=len;i++) { add(0,i,(s[i]-'a')*Hash[i]); add(1,len+1-i,(s[i]-'a')*Hash[len+1-i]); } int T; cin >> T; while(T--) { char c[5]; scanf("%s",c); if(c[0]=='C') { char b[5]; int a; scanf("%d%s",&a,b); add(0,a,(b[0]-s[a])*Hash[a]); add(1,len+1-a,(b[0]-s[a])*Hash[len+1-a]); s[a]=b[0]; } else { int l,r; scanf("%d%d",&l,&r); if(gethash(0,l,r)*Hash[len-r]==gethash(1,len+1-r,len+1-l)*Hash[l-1])//采用交叉相乘把除换成了乘 puts("yes"); else puts("no"); } } } return 0; }
AC dreamoj 1011 树状数组+hash维护字符串的前缀和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。