URAL-1989 Subpalindromes 多项式Hash+树状数组

时间：2022-07-18 23:27:46

　　题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1989

　　题意：给出一个字符串，m个操作：1,修改其中一个字符串，2,询问 [a, b] 是不是回文串。数据范围10^5。

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

 //STATUS:C++_AC_140MS_2777KB

 #include <functional>

 #include <algorithm>

 #include <iostream>

 //#include <ext/rope>

 #include <fstream>

 #include <sstream>

 #include <iomanip>

 #include <numeric>

 #include <cstring>

 #include <cassert>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <bitset>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 //#pragma comment(linker,"/STACK:102400000,102400000")

 //using namespace __gnu_cxx;

 //define

 #define pii pair<int,int>

 #define mem(a,b) memset(a,b,sizeof(a))

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define PI acos(-1.0)

 //typedef

 typedef __int64 LL;

 typedef unsigned __int64 ULL;

 //const

 const int N=;

 const int INF=0x3f3f3f3f;

 const int MOD=,STA=;

 const LL LNF=1LL<<;

 const double EPS=1e-;

 const double OO=1e15;

 const int dx[]={-,,,};

 const int dy[]={,,,-};

 const int day[]={,,,,,,,,,,,,};

 //Daily Use ...

 inline int sign(double x){return (x>EPS)-(x<-EPS);}

 template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}

 template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}

 template<class T> inline T lcm(T a,T b,T d){return a/d*b;}

 template<class T> inline T Min(T a,T b){return a<b?a:b;}

 template<class T> inline T Max(T a,T b){return a>b?a:b;}

 template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}

 template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}

 template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}

 template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}

 //End

 ULL bit[N],c[N][];

 char s[N];

 int n,len;

 inline int lowbit(int x)

 {

     return x&(-x);

 }

 void update(int x,ULL val,int flag)

 {

     while(x<=len){

         c[x][flag]+=val;

         x+=lowbit(x);

     }

 }

 ULL sum(int x,int flag)

 {

     ULL ret=;

     while(x){

         ret+=c[x][flag];

         x-=lowbit(x);

     }

     return ret;

 }

 int main()

 {

  //   freopen("in.txt","r",stdin);

     int i,j,w,L,R;

     char op[],ch;

     bit[]=;

     for(i=;i<N;i++)bit[i]=bit[i-]*;

     while(~scanf("%s",s))

     {

         len=strlen(s);

         mem(c,);

         for(i=;i<len;i++){

             update(i+,(s[i]-'a'+)*bit[i],);

             update(i+,(s[len-i-]-'a'+)*bit[i],);

         }

         scanf("%d",&n);

         while(n--){

             scanf("%s",op);

             if(op[]=='p'){

                 scanf("%d%d",&L,&R);

                 ULL a=(sum(R,)-sum(L-,))*bit[len-R];

                 ULL b=(sum(len-L+,)-sum(len-R,))*bit[L-];

                 if(a==b)printf("Yes\n");

                 else printf("No\n");

             }

             else {

                 scanf("%d %c",&w,&ch);

                 update(w,(ch-s[w-])*bit[w-],);

                 update(len-w+,(ch-s[w-])*bit[len-w],);

                 s[w-]=ch;

             }

         }

     }

     return ;

 }

相关文章