BZOJ[2780][Spoj]8093 Sevenk Love Oimaster 后缀数组-白红宇

BZOJ[2780][Spoj]8093 Sevenk Love Oimaster 后缀数组

阅读量：7125 次

发布时间：2019-06-28

本文共 4423 字，大约阅读时间需要 14 分钟。

此题精神AC

SAM水题，但是我不会SAM

将所有串串在一起，对这个大串求SA

对于每一个模式串，能匹配的都是在rk意义上连续的一段

二分出这一段的左右端点

现在要做的就是统计这段区间有多少不同的颜色

然后就同呵呵的项链

我就是要用莫队来做(UPD 发blog10min以后：BIT也过不了)

本机300ms，校OJ 700msA了

能用的卡常技巧我都用了

这篇博客留着等以后卡常的时候参考

代码如下：

莫队

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #pragma GCC optimize(3)#pragma GCC optimize(2)#define N 600050using namespace std;inline char nc(){    static char buf[1000000],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}inline int read(){    register int x=0,f=1;char c;    do c=nc(),f=c=='-'?-1:f; while(!isdigit(c));    do x=(x<<3)+(x<<1)+c-'0',c=nc(); while(isdigit(c));    return x*f;}int n,m,top,t,tot,len,l,r,mid,Block_Size,tmp,top1;typedef int iarr[N];iarr a,SA,rk,buck,las,height,ans,L,R,pw,block,num,s1;int f[N][25];char s[N];inline int Max(int a,int b){return a>b?a:b;}inline int Min(int a,int b){return a
         
          =1;--i) SA[buck[rk[las[i]]]--]=las[i]; top=m=0;}inline void Get_SA(){ for(register int i=1;i<=n;++i){ rk[i]=s[i];las[i]=i; } m=127;Radix_Sort(); for(register int i=1;m^n;i<<=1){ for(register int j=n-i+1;j<=n;++j) las[++top]=j; for(register int j=1;j<=n;++j) if(SA[j]>i) las[++top]=SA[j]-i; Radix_Sort(); for(register int j=1;j<=n;++j) las[j]=rk[j]; for(register int j=1;j<=n;++j) rk[SA[j]]=judge(SA[j-1],SA[j],i)?m:++m; } for(register int i=1,j=0;i<=n;++i,j=j?j-1:0){ while(s[i+j]==s[SA[rk[i]-1]+j]) ++j; height[rk[i]]=j; }}inline void Get_ST(){ pw[0]=1; for(register int i=1;pw[i-1]<=n;++i) pw[i]=1<
          
           y) swap(x,y); int t=log2(y-x+1); return Min(f[x][t],f[y-pw[t]+1][t]);}struct Query{ int l,r,id;}q[N];inline bool cmp(Query a,Query b){ return block[a.l]==block[b.l]?a.r
           
            
             >1; if(LCP(mid+1,L[i])>=len) q[i].l=mid,r=mid-1; else l=mid+1; } l=L[i]+1;r=n; if(height[L[i]+1]
             
              >1; if(LCP(L[i]+1,mid)>=len) q[i].r=mid,l=mid+1; else r=mid-1; } q[i].id=i; } sort(q+1,q+tot+1,cmp); l=1;r=0; for(register int i=1;i<=tot;i++){ while(l
              
               q[i].l) Update(a[SA[--l]],1); while(r
               
                q[i].r) Update(a[SA[r--]],-1); ans[q[i].id]=tmp; } for(register int i=1;i<=tot;i++){ printf("%d\n",ans[i]); } return 0;}

BIT

#include
    
     #include
     
      #pragma GCC optimize(3)#define isdigit(c) (c>='0' && c<='9')#define isalpha(c) (c>='a' && c<='z')#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)#define judge(a,b,c) (las[a]==las[b] && las[a+c]==las[b+c])#define Swap(a,b) (a=a^b,b=a^b,a=a^b)#define Min(a,b) (a
      
       =1;--i) SA[buck[rk[las[i]]]--]=las[i];    top=m=0;}inline void Get_SA(){    register int i,j;    for(i=1;i<=n;++i){        rk[i]=s[i];las[i]=i;    }    m=127;Radix_Sort();    for(i=1;m^n;i<<=1){        for(j=n-i+1;j<=n;++j) las[++top]=j;        for(j=1;j<=n;++j) if(SA[j]>i) las[++top]=SA[j]-i;        Radix_Sort();        for(j=1;j<=n;++j) las[j]=rk[j];        for(j=1;j<=n;++j) rk[SA[j]]=judge(SA[j-1],SA[j],i)?m:++m;    }    for(i=1,j=0;i<=n;++i,j=j?j-1:0){        while(s[i+j]==s[SA[rk[i]-1]+j]) ++j;        height[rk[i]]=j;    }}inline void Get_ST(){    pw[0]=1;    register int i,j;    for(i=1;pw[i-1]<=n;++i){        pw[i]=1<
       
        y) Swap(x,y);    register int t=log2[y-x+1];    return Min(f[t][x],f[t][y-pw[t]+1]);}struct Query{    int l,r,id;}q[N];inline char cmp(register Query a,register Query b){    return a.l
        
         n) break;        do s[++top]=nc(),a[top]=i+1; while(isalpha(s[top]));        s[top]=126;    }    for(i=1;i<=tot;i+=2){        L[i]=top+1;        do s[++top]=nc(); while(isalpha(s[top]));        R[i]=top-1;        s[top]=126;        if(i+1>tot) break;        L[i+1]=top+1;        do s[++top]=nc(); while(isalpha(s[top]));        R[i+1]=top-1;        s[top]=126;    }    n=top;    Get_SA();Get_ST();    for(i=1;i<=tot;++i){        len=R[i]-L[i]+1;        L[i]=rk[L[i]];        l=1;r=L[i]-1;        if(height[L[i]]
         
          >1; if(LCP(mid+1,L[i])>=len) q[i].l=mid,r=mid-1; else l=mid+1; } l=L[i]+1;r=n; if(height[L[i]+1]
          
           >1; if(LCP(L[i]+1,mid)>=len) q[i].r=mid,l=mid+1; else r=mid-1; } q[i].id=i; } sort(q+1,q+tot+1,cmp); for(i=n;i>=1;i-=2){ if(a[SA[i]]) nex[i]=b[a[SA[i]]],b[a[SA[i]]]=i; if(i-1>=1 && a[SA[i-1]]) nex[i-1]=b[a[SA[i-1]]],b[a[SA[i-1]]]=i-1; } for(i=1;i<=maxx;i+=2){ if(b[i]) Add(b[i],1); if(i+1<=maxx && b[i+1]) Add(b[i+1],1); } l=1; for(i=1;i<=tot;i+=2){ while(l
           
            tot){ break; } while(l