[Gym 102114J]Just So You Know

Link

字符集出这么大的范围卡后缀自动机有点令人不适。

Solution

题意为给定一个字符串,找出所有不同的子串并统计其出现次数,并以出现次数为频率将所有的子串做哈夫曼编码的编码长度。
第一步,要求出,出现次数为i的子串的个数c_i。如果使用后缀自动机,可以对于每个状态求出Right集合R的大小,那么一个状态p就会对i=|R|c_i带来p->maxRight-p->par->maxRight的贡献。
但是由于\Sigma特别大,这样会MLE。
tls给的做法是用后缀数组构建出后缀树然后在后缀树上做统计。考虑后缀树的一条长度为l的边,那么从根到这条边上的l个字符可以产生l个子串。假设这条边下方有k个后缀的终点,那么就会有k个后缀满足这l个子串是他们的前缀,也就是说,这l个子串都出现了k次。因此,就会对c_k带来l的贡献。
接下来,就是求出哈夫曼编码的权值。
哈夫曼编码,在频率升序存储的前提下,有线性的做法。开两个队列,一开始将所有字符的频率扔到Q_1,然后循环到\rm{size}(Q_1)+\rm{size}(Q_2)=1为止。每次循环,从两个队列的队首取两次最小值,然后将和插到Q_2末尾。显然,取出的两个值的和是不下降的,Q_2序列一定是有序的,算法正确性显然。
在本问题中,对于i\le n的部分,直接扫一遍c_i数组,模拟堆的操作就好了。对于合并产生的值v,如果v\le n,就还是将频率累加到c_v待以后处理,否则,就将v插入到Q_1中。
最终,Q_1中的元素是有序的。另外,因为Q_1中每个元素的权值都>n,且所有元素的权值和\le \frac {n(n+1)} 2,所以Q_1中的元素个数为O(n)
接下来套用如上算法就可以O(n)解决求最优编码部分。
后缀数组转后缀树的复杂度为O(n),采用O(n)的后缀数组实现,则总复杂度为O(n)

Code

#include <bits/stdc++.h>

const int XN=2e6+11;

//(v,c) v->O(n)
long long times[XN];

std::vector<int> SAIS(std::vector<int> &s,int sig) {
    enum Type { L,S };

    int n=s.size();
    std::vector<Type> type(n);
    std::vector<int> sa(n),cnt(sig),lp(sig),sp(sig);

    auto LMS=[&](int x) {
        return x>0 && type[x]==S && type[x-1]==L;
    };

    auto Induce=[&]() {
        for(int i=0;i<sig;++i)
            lp[i]=i?cnt[i-1]:0;
        for(int i=0;i<n;++i)
            if(sa[i]>0 && type[sa[i]-1]==L)
                sa[lp[s[sa[i]-1]]++]=sa[i]-1;
        for(int i=0;i<sig;++i)
            sp[i]=cnt[i]-1;
        for(int i=n-1;i>0;--i)
            if(sa[i]>0 && type[sa[i]-1]==S)
                sa[sp[s[sa[i]-1]]--]=sa[i]-1;
    };

    type[n-1]=S;
    for(int i=n-2;i>=0;--i)
        type[i]=s[i]<s[i+1] || (s[i]==s[i+1] && type[i+1]==S)?S:L;
    for(int x : s)
        cnt[x]++;
    for(int i=1;i<sig;++i)
        cnt[i]+=cnt[i-1];
    std::vector<int> lms;
    for(int i=0;i<n;++i)
        if(LMS(i))
            lms.push_back(i);
    for(int i=0;i<sig;++i)
        sp[i]=cnt[i]-1;
    std::fill(sa.begin(),sa.end(),-1);
    for(int i : lms)
        sa[sp[s[i]]--]=i;
    Induce();
    std::vector<int> id(n,-1);
    int c=0;
    for(int i=0,last=-1;i<n;++i)
        if(LMS(sa[i])) {
            auto Equal=[&](int x,int y)->bool {
                do if(s[x++]!=s[y++]) return 0;
                while(!LMS(x) && !LMS(y));
                return s[x]==s[y];
            };
            id[sa[i]]=last!=-1 && Equal(sa[i],last)?c-1:c++;
            last=sa[i];
        }

    std::vector<int> s1;
    for(int i=0;i<n;++i)
        if(id[i]!=-1)
            s1.push_back(id[i]);
    std::vector<int> sa1(c);
    if(c==(int)lms.size())
        for(int i=0;i<c;++i)
            sa1[s1[i]]=i;
    else
        sa1=SAIS(s1,c);
    for(int i=0;i<sig;++i)
        sp[i]=cnt[i]-1;
    std::fill(sa.begin(),sa.end(),-1);
    for(int i=lms.size()-1;i>=0;--i)
        sa[sp[s[lms[sa1[i]]]]--]=lms[sa1[i]];
    Induce();
    return sa;
}

int n;
std::vector<int> sa,rank,height;

struct Edge {
    int to,v;
};

std::vector<Edge> G[XN];
int root,pcnt,last,dis[XN],fa[XN],size[XN];

int NewNode() {
    G[++pcnt].clear();
    size[pcnt]=fa[pcnt]=dis[pcnt]=0;
    return pcnt;
}

void AddEdge(int x,int y,int v) {
    G[x].push_back({y,v});
    dis[y]=dis[fa[y]=x]+v;
}

void Build() {
    pcnt=0;
    root=NewNode();
    AddEdge(root,last=NewNode(),n-sa[1]+1);
    size[last]=1;
    for(int i=2;i<=n;++i) {
        int p=last,np=NewNode();
        while(dis[p]>height[i])
            p=fa[p];
        if(dis[p]!=height[i]) {
            int d=height[i]-dis[p],o=NewNode();
            auto e=G[p].back();
            G[p].pop_back();
            AddEdge(p,o,d);
            AddEdge(o,e.to,e.v-d);
            p=o;
        }
        AddEdge(p,np,n-sa[i]+1-height[i]);
        size[last=np]=1;
    } 
}

void DFS(int pos) {
    for(Edge &e : G[pos]) {
        DFS(e.to);
        size[pos]+=size[e.to];
        times[size[e.to]]+=e.v;
    }
}

void Work() {
    std::cin>>n;
    std::vector<int> a(n+1);
    for(int i=1;i<=n;++i) {
        std::cin>>a[i-1];
        a[i-1]++;
        times[i]=0;
    }
    a[n]=0;
    sa=SAIS(a,100+1);
    a.insert(a.begin(),0);
    rank.resize(n+1);
    height.resize(n+1);
    for(int i=1;i<=n;++i)
        rank[++sa[i]]=i;
    for(int i=1,len=0;i<=n;++i)
        if(rank[i]!=1) {
            int j=sa[rank[i]-1];
            while(a[i+len]==a[j+len]) ++len;
            height[rank[i]]=len;
            if(len) len--;
        }

    Build();
    DFS(root);

    long long sum=0,cnt=(long long)n*(n+1)/2;
    std::deque<long long> Q1,Q2;

    for(int i=1;i<=n;)
        if(times[i]) {
            if(times[i]==1) {
                int j=i+1;
                while(j<=n && !times[j])
                    ++j;
                if(j<=n) {
                    times[j]--;
                    if(i+j<=n)
                        times[i+j]++;   
                    else
                        Q1.push_back(i+j);
                    sum+=i+j;
                } else
                    Q1.push_front(i);
                times[i++]--;
            } else {
                sum+=i*2ll*(times[i]/2);
                if(i*2<=n)
                    times[i*2]+=times[i]/2;
                else
                    for(int t=times[i]/2;t--;Q1.push_back({i*2}));
                times[i]%=2;
            }
        } else
            i++;
    while(Q1.size()+Q2.size()>1) {
        long long a[2];
        for(int i=0;i<2;++i) {
            if(Q1.size() && (Q2.empty() || Q1.front()<Q2.front())) {//NAIVE
                a[i]=Q1.front();
                Q1.pop_front();
            } else {
                a[i]=Q2.front();
                Q2.pop_front();
            }
        }
        sum+=a[0]+a[1];
        Q2.push_back(a[0]+a[1]);
    }

    long long d=std::__gcd(sum,cnt);
    long long p=sum/d,q=cnt/d;
    if(q==1)
        std::cout<<p<<'\n';
    else
        std::cout<<p<<'/'<<q<<'\n';
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注