ABC353E 题解

xiaofu15191 · 2024-05-11 22:45:57 · 题解

首先对 (S_1, \ldots, S_N) 排序。

对于一个字符串 S_i，考虑从 1 至 len_{S_i} 枚举 j。在 i+1 至 lastpos 中二分，其中 lastpos 的含义稍后再讲。

二分找到第 j 个字符相同且最靠后的 S_k，随后将 k 赋给 lastpos。

现在 lastpos 的含义就很明朗了：因为只有前 j-1 个字符相同作为公共前缀，第 j 个字符才可能继续更新公共前缀的长度。所以我们将上一次的 k 记录下来，缩小下一次的二分范围。

对于每一个 j，记录下对应的 k 加入 pos 数组中。注意最后要在 pos 数组中加入 i。那么对于一个 S_i ，我们就能计算其对答案的贡献 W_i：

最后将 W_i 相加即可。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int n;
string s[300010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+n+1);
    long long ans=0;
    for(int i=1;i<n;i++)
    {
        int lastpos=n;
        vector<int>pos;
        for(int j=0;j<s[i].size();j++)
        {
            int l=i+1,r=lastpos;
            lastpos=0;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(s[mid][j]<=s[i][j])
                {
                    l=mid+1;
                    if(s[mid][j]==s[i][j]) lastpos=max(lastpos,mid);
                }
                else r=mid-1;
            }
            if(lastpos==0) break;
            pos.push_back(lastpos);
        }
        pos.push_back(i);
        for(int j=0;j<pos.size()-1;j++) ans+=(pos[j]-pos[j+1])*(j+1);
    }
    printf("%lld\n",ans);
}