E. Kefa and Watch hash 线段树

2015-09-28 14:11:36 by opas
这题给的是一个字符串把其中一些子串给取出来判断是否是周期为d的字符串还需要把其中的一个区间完全变成一个数，然后在查询，我们把每个字符串进行hash 不管结果怎么样hash 然后进行区区间判断。。还是存在概率性的错误的
#include <algorithm>

#include <string.h>

#include <cstdio>

#include <vector>

using namespace std;

typedef long long LL;

const int maxn=;

const LL mod0 =;

const LL mod1 =;

LL powd[][maxn],digitpow[][][maxn];

void init()

{

   powd[][]=powd[][]=;

   for(LL i=; i<=; i++)

    {

         powd[][i]=( powd[][i-] *  )%mod0;

         powd[][i]=( powd[][i-] *  )%mod1;

         for(int j=; j<; j++)

            {

                digitpow[][j][i]=( digitpow[][j][i-]*+j )%mod0;

                digitpow[][j][i]=( digitpow[][j][i-]*+j )%mod1;

            }

    }

}

char str[maxn];

struct Itree

{

       LL mark[maxn*],v[][maxn*],ans[];

       int cL,cR,num;

       void maintain(int L, int R, int o)

       {

            int mid=(L+R)>>;

            v[][o]=( v[][o*] * powd[][R-mid] + v[][o*+] )%mod0;

            v[][o]=( v[][o*] * powd[][R-mid] + v[][o*+] )%mod1;

       }

       void build(int L, int R, int o)

       {

            mark[o]=-;

            if(L==R){

                v[][o]=v[][o]=str[L-]-''; return ;

            }

            int mid=(L+R)>>;

            build(L,mid,o*);

            build(mid+,R,o*+);

            maintain(L,R,o);

       }

       void qper(int L, int R,int n, LL &ans0,LL &ans1)

       {

            cL=L;cR=R; ans[]=ans[]=;num=;

            query(,n,);

            ans0=ans[]; ans1=ans[];

       }

       void pushdown(int L, int R, int o)

       {

            if(mark[o]!=-)

                {

                       int mid=(L+R)>>;

                       mark[o*]=mark[o*+]=mark[o];

                       v[][o*]=digitpow[][mark[o]][ mid-L+ ];

                       v[][o*]=digitpow[][mark[o]][ mid-L+ ];

                       v[][o*+]=digitpow[][mark[o]][ R-mid ];

                       v[][o*+]=digitpow[][mark[o]][ R-mid ];

                       mark[o]=-;

                }

       }

       void query(int L, int R, int o)

       {

            if(cL<=L&&R<=cR)

            {

                 ans[]=(ans[]*powd[][R-L+]+v[][o])%mod0;

                 ans[]=(ans[]*powd[][R-L+]+v[][o])%mod1;

                return ;

            }

            pushdown(L,R,o);

            int mid=(L+R)>>;

            if(cL<=mid)query(L,mid,o*);

            if(cR>mid)query(mid+,R,o*+);

       }

       void update(int L, int R, int o)

       {

            if(cL<=L&&R<=cR)

                {

                    mark[o]=num;

                    v[][o]=digitpow[][num][R-L+];

                    v[][o]=digitpow[][num][R-L+];

                    return ;

                }

             pushdown(L,R,o);

             int mid=(L+R)>>;

             if(cL<=mid)update(L,mid,o*);

             if(cR>mid)update(mid+,R,o*+);

             maintain(L,R,o);

       }

}T;

int main()

{

     init();

     int n,m,k;

     while(scanf("%d%d%d",&n,&m,&k)==)

        {

            scanf("%s",str);

            T.build(,n,);

            m+=k;

            while(m--){

                int op,L,R,V;

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

                 if(op==){

                  T.cL=L;T.cR=R;  T.num=V;

                  T.update(,n,);

                 }else{

                     if((R-L+)<=V){

                        puts("YES");

                     }else

                     if( ( R - L +  ) <=  * V )

                        {

                             int len=R-L+-V;

                             LL a10,a11,a20,a21;

                             T.qper(L,L+len-,n,a10,a11);

                             T.qper(R-len+,R,n,a20,a21);

                             if(a10==a20&&a11==a21) puts("YES");

                             else puts("NO");

                        }else

                        {

                            if((R-L+)%V == ){

                              int d=(R-L+)/V;

                              int len = (d-)*V;

                              LL a10,a11,a20,a21;

                              T.qper(L,L+len-,n,a10,a11);

                              T.qper(R-len+,R,n,a20,a21);

                              if(a10==a20&&a11==a21) puts("YES");

                              else puts("NO");

                            }

                            else{

                              int d=(R-L+)/V;

                              int len = (d-)*V;

                              int tail=(R-L+)-V*d;

                              LL a10,a11,a20,a21;

                              T.qper(L,L+len-,n,a10,a11);

                              T.qper(L+V,L+V+len-,n,a20,a21);

                              if(a10==a20&&a11==a21) {

                                 T.qper(L,L+tail-,n,a10,a11);

                                 T.qper(R-tail+,R,n,a20,a21);

                                 if(a10==a20&&a11==a21)

                                    puts("YES");

                                 else puts("NO");

                              }

                              else puts("NO");

                            }

                        }

                 }

                }

        }

    return ;

}
巴特西

E. Kefa and Watch hash 线段树

最新文章

热门文章
