3572. 【GDKOI2014】基因模式 (Standard IO)

Time Limits: 

1000 ms  Memory Limits: 262144 KB     

Description

 

Input

Output

对于每个询问，输出一行，表示对应的询问中符合要求的子串数目。

注意两个子串在S中位于不同位置即视为不同子串，即使它们对应的序列相同。

空串不计算在内。

 

Sample Input

输入1：

3

GATATG

ATA

a

GATAT

a

GATATG

aT

输入2：

2

ACTG

ACTGACTG

A

ACTGACTG

a

Sample Output

输出1：

2

7

5

输出2：

8

12

 

Data Constraint

 

对于询问串S,定义near[i]为以第i位为起点同时为T的子串的最长串的长度，则Si-i+near[i]-1串的任一子串都为T的子串

求解near的过程用SA和rmq实现

然后用一个二进制数表示对各个字母的奇偶性要求。f[i]表示以满足奇偶性为i的字符串数

对于第i位，为S子串的起点和终点为i和i+near[i]-1，这两个值都单调不下降。

对于末尾的转移，设x为后一位字母用二进制表示的奇偶性，f[i]=f'[i^x]，且f[x]=f[x]+1（表示增加这一位的单个字符串）

对于首的转移，在对应位减一即可

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int i,t,n,mj,ext,mn,x,len,j;int sa[300011],rank[300011],h[300011],co[300011],nr[300011];int a[300011],b[300011],near[300011],f[3][30],bel[300011],ans[1011];int lef[300011],rig[300011];char s[300011],s1[1011];bool p[1011][5];struct tree{    int x,z,q;}tr[1200011];void Read(){    char c;    while(c=getchar(),c<'A'||c>'Z');    s[++n]=c;    bel[n]=i;    while(c=getchar(),c>='A'&&c<='Z'){        s[++n]=c;        bel[n]=i;    }}void sort(int *a){    int i;    for(i=0;i<=mn;i++)co[i]=0;    for(i=1;i<=n;i++)co[a[i]+1]++;    for(i=1;i<=mn;i++)co[i]+=co[i-1];    for(i=1;i<=n;i++)nr[i]=0;    for(i=1;i<=n;i++){        co[a[sa[i]]]++;        nr[co[a[sa[i]]]]=sa[i];    }    for(i=1;i<=n;i++)sa[i]=nr[i];}void getrank(){    int i;    x=0;    for(i=1;i<=n;i++){        if(i==1||a[sa[i]]!=a[sa[i-1]]||b[sa[i]]!=b[sa[i-1]])x++;        rank[sa[i]]=x;    }    mn=x;}void Suffix(){    int i,j,k,l,last;    for(i=1;i<=n;i++){        if(s[i]!='#')a[i]=s[i]-64;        b[i]=0;        sa[i]=i;    }    sort(a);    getrank();    l=1;    while(x!=n){        for(i=1;i<=n;i++){            a[i]=rank[i];            if(i+l<=n)b[i]=rank[i+l];            else b[i]=0;        }        sort(b);        sort(a);        getrank();        l*=2;    }    last=0;    for(i=1;i<=n;i++){        if(last)last--;        if(rank[i]==1)continue;        j=i;        k=sa[rank[i]-1];        while(j+last<=n&&k+last<=n&&s[j+last]==s[k+last]&&s[j+last]!='#')last++;        h[rank[i]]=last;    }}void build(int l,int r,int t){    int mid;    if(l==r){        tr[t].x=l;        tr[t].z=r;        tr[t].q=h[l];        return;    }    tr[t].x=l;    tr[t].z=r;    mid=(l+r)/2;    build(l,mid,t+t);    build(mid+1,r,t+t+1);    tr[t].q=min(tr[t+t].q,tr[t+t+1].q);}int ask(int l,int r,int t){    int mid;    if(l==tr[t].x&&r==tr[t].z)return tr[t].q;    mid=(tr[t].x+tr[t].z)/2;    if(r<=mid)return ask(l,r,t+t);    if(l>mid)return ask(l,r,t+t+1);    if(l<=mid&&r>mid)return min(ask(l,mid,t+t),ask(mid+1,r,t+t+1));}void Work(int x){    int i,j,k,l,rn,xzq,ap,ple,z,q,xz,r,e;    bool pp;    xzq=0;    for(i=mj;i<=n;i++){        if(bel[i]!=x)break;        rn=i-mj+1;        l=lef[rank[i]];        r=rig[rank[i]];        if(l!=0){            if(l
         
          ple)near[rn]=ap;        else near[rn]=ple;    }    for(i=0;i<=15;i++){        f[0][i]=0;        f[1][i]=0;    }    z=0;    l=1;    for(i=mj;i<=n;i++){        if(bel[i]!=x)break;        rn=i-mj+1;        if(rn!=1){            f[1-l][z]--;            if(s[i-1]=='A')z^=1;            if(s[i-1]=='G')z^=2;            if(s[i-1]=='C')z^=4;            if(s[i-1]=='T')z^=8;        }        for(j=rn-1+near[rn-1];j
          
           =1;i--){ if(bel[sa[i]]==0)rig[i]=i; else rig[i]=rig[i+1]; } build(1,n,1); for(i=1;i<=t;i++)Work(i);}