P7937 [COCI2007-2008#5] BAZA 题解

· · 题解

背景：校内模拟赛出过这题的弱化版，当时 trie+unrodered_map 这种大空间的东西都放过了，时间缩紧了，要求 O(|\sum|) 。现在回来做这个卡空间的版本。

解法

把每个串都用 '{' 填充为长度 30 的串（其他字符不知道能不能满足答案，'{' 的 ASCII 码比 'z' 大 1）。

把所有串按前 1 位前缀，前 2 位前缀，...，前 30 位前缀排序。

对于所有和原来第 j 个串前 i 为前缀相同的串（包括自己），记录：这样的串的个数（直接求即可），记为 f_{i,j}；这样的串有多少个在 j 前面（包括自己，用树状数组求），记为 g_{i,j}。

每次查询也像上面那样填充。先二分前 30 位前缀判断给定串中等于查询串的串最小的位置（或报告没有）。

1.若给定串中有等于查询串的串。

设最小位置为 x，那么对于所有 i 统计给定的串有多少个和查询串恰有前 i 位都一样，且位置在 x 前面。这个个数设为 F_i 。则答案就是 \sum\limits_{i=1}^{30} i\times F_i+x。

刚才记录的 g_{i,x} 表示有多少个串恰有前 i,i+1,...,30 位与 x 相同且位置 \le j。对 g_{,x} 做差分（即 g_{i,x} 减去 g_{i+1,x}）后 g_{,x} 就是 F 了。

有一个细节，设查询串大小为 len，这里第 x 个串对答案的贡献变成了 30，因为我们填充了。把 F_{len} 加上 1 ，F_{30} 减 1 为 0，然后统计答案即可，这里串长是小于 30 于是不会影响答案。

2.若给定串中没有等于查询串的串。

对于所有 i 二分前 i 位前缀找出任意一个前 i 位前缀和查询串相同的串，记这个位置为 y（没有的话就对答案没有贡献了），设 u_{i}=f_{i,y}。

把 u 差分，把 u_{len} 加上 1 ，u_{30} 减 1 为 0。同上能得到答案为：\sum\limits_{i=1}^{30} i\times u_i+n。直接统计即可。

复杂度 O(n\log^2 n) (把 30 视作与 \log n 同阶)，空间是 O(n)，有 30 倍常数。

丑陋的代码：

#include<bits/stdc++.h>
#define P pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=3e4+5;
int n,m,t,b[35][N],c[35][N],tt[35],fir[N],d[N],e[35][N],ans,u[35],L,v[35][N];
char a[N][35],f[35];
vector<P>g;
inline int lb(int x){return x&-x;}
inline void add(int wz,int x){for(;wz<=n;wz+=lb(wz)) d[wz]+=x;}
inline int ask(int wz){int s=0;for(;wz;wz-=lb(wz)) s+=d[wz];return s;}
inline bool cmp(int x,int y){return a[x][t]<a[y][t];}
inline bool eq(char *A,char *B,int x)
{
    for(int i=0;i<=x;i++) if(A[i]!=B[i]) return 0;
    return 1;
}
inline bool xd(char *A,char *B,int x)
{
    for(int i=0;i<=x;i++)
    {
        if(A[i]<B[i]) return 1;
        if(A[i]>B[i]) return 0;
    }
    return 1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a[i]),t=strlen(a[i]);
        for(int j=t;j<30;j++) a[i][j]='{';
    }
    for(int i=1;i<=n;i++) b[0][i]=i;g.push_back({1,n});
    for(t=0;t<30;t++)
    {
        for(int i=1;i<=n;i++) b[t+1][i]=b[t][i];//只有b的t +1 
        for(P &i:g) sort(b[t+1]+i.fi,b[t+1]+i.se+1,cmp);
        for(int i=1;i<=n;i++)
        {
            if(i==1||!eq(a[b[t+1][i-1]],a[b[t+1][i]],t)) c[t][++tt[t]]++,fir[tt[t]]=i;
            else c[t][tt[t]]++;
        }g.clear();
        for(int i=1;i<=tt[t];i++) g.push_back({fir[i],fir[i]+c[t][i]-1});
        for(P &i:g)
        {
            for(int j=i.fi;j<=i.se;j++) add(b[t+1][j],1);
            for(int j=i.fi;j<=i.se;j++) e[t][b[t+1][j]]=ask(b[t+1][j]),v[t][b[t+1][j]]=i.se-i.fi+1;
            for(int j=i.fi;j<=i.se;j++) add(b[t+1][j],-1);
        }
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",f);L=strlen(f);for(int i=L;i<30;i++) f[i]='{';ans=0;
        int l=1,r=n,mid;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(xd(f,a[b[30][mid]],29)) r=mid-1,t=mid;
            else l=mid+1;
        }
        if(!eq(f,a[b[30][t]],29)) t=-1;memset(u,0,sizeof(u));
        if(t!=-1)
        {
            t=b[30][t];for(int i=0;i<30;i++) u[i]=e[i][t];
            for(int i=0;i<29;i++) u[i]-=u[i+1];u[L-1]+=u[29];u[29]=0;
            for(int i=0;i<30;i++) ans+=(i+1)*u[i];
            printf("%d\n",ans+t);
        }
        else
        {
            for(int i=0;i<30;i++)
            {
                int l=1,r=n,mid;
                while(l<=r)
                {
                    mid=(l+r)>>1;
                    if(xd(f,a[b[i+1][mid]],i)) r=mid-1,t=mid;
                    else l=mid+1;
                }
                if(eq(f,a[b[i+1][t]],i)) t=b[i+1][t],u[i]=v[i][t];
                else break;
            }
            for(int i=0;i<29;i++) u[i]-=u[i+1];
            for(int i=0;i<30;i++) ans+=(i+1)*u[i];
            printf("%d\n",ans+n);
        }
    }
    return 0;
}