CF386C

_edge_ · 2022-07-22 18:41:26 · 题解

题意

其实可以发现，我们先枚举右端点的话，对于不同的 d 的值，左端点的数量仅仅有 26 个。

什么意思呢？就是说，对于很多左端点来说，他们到右端点的子串 d 的值是类似的。

然后我们发现这个东西它具有单调性，可以进行二分，具体的，对于以右端点 i 开始的，每一段都二分一下最远的左端点，然后记录前缀和 check。

然而过不去。

#include <iostream>
#include <cstdio>
#define int long long 
using namespace std;
const int INF=3e5+5;
string s1;
int sum[INF][35],t[35];
int check(int l,int r) {
//  cout<<l<<" "<<r<<" "<<"bomb\n";
    int ans=0;
    for (int i=0;i<26;i++)
        if (sum[r][i]-sum[l-1][i]) ans++;
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>s1;int len=s1.size();s1=" "+s1;
    for (int i=1;i<=len;i++) {
        for (int j=0;j<26;j++) 
            sum[i][j]=sum[i-1][j]+((s1[i]-'a')==j);
    }

    for (int i=1;i<=len;i++) {
        int j=i;
        while (j>=1) {
            int l=1,r=j,ans=-1,xx=check(j,i);
            while (l<=r) {
                int Mid=(l+r)>>1;
                if (check(Mid,i)==xx) r=(ans=Mid)-1;
                else l=Mid+1;
            }
            t[xx]+=j-ans+1;
            j=ans-1;
//          cout<<j<<" "<<ans<<" ??\n";
        }
    }

    cout<<check(1,len)<<"\n";

    for (int i=1;i<=26;i++)
        if (t[i]) cout<<t[i]<<"\n";
    return 0;
}

可惜，这里是 3 \times 10^5 ，我本地跑大约是 2.5s，CF 上的远古题时限都比较紧，所以过不去。

然后我们考虑如何优化这个过程，我们发现这个复杂度的瓶颈出在二分以及 check。

假如说我们以及知道了要记录的 d 的值，似乎可以做一点？

考虑枚举这个 d 的值，然后再去枚举左端点，发现这个东西仍然具有单调性，并且很好用双指针去维护。

但是这题稍微有点烦，因为它双指针需要记录相同的数量。

如果仅仅跑的最后一个相同的，然后跑回来，那肯定会 TLE 起飞。

考虑用两个双指针，一个指向第一个，另外一个指向最后一个。

和莫队的想法一样，对于新出现的字符加到一个桶里面，然后就可以很快速的查询当前区间出现字符。

#include <iostream>
#include <cstdio>
#define int long long 
using namespace std;
const int INF=3e5+5;
string s1;
int sum[INF][35],t[35],la[35],la1[35];
int check(int l,int r) {
//  cout<<l<<" "<<r<<" "<<"bomb\n";
    int ans=0;
    for (int i=0;i<26;i++)
        if (sum[r][i]-sum[l-1][i]) ans++;
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>s1;int len=s1.size();s1=" "+s1;
    for (int i=1;i<=len;i++) {
        for (int j=0;j<26;j++) 
            sum[i][j]=sum[i-1][j]+((s1[i]-'a')==j);
    }

    for (int i=1;i<=26;i++) {
        int j1=0,j2=0,sum1=0,sum2=0;
        for (int k=1;k<=len;k++) {
            j1=max(j1,k-1);j2=max(j2,k-1);
            while (j1+1<=len && sum1<=i) {
                if (la[s1[j1+1]-'a']==0 && sum1==i) break;
                la[s1[j1+1]-'a']++;
                if (la[s1[j1+1]-'a']==1) sum1++;
                j1++;
            }
//          if (sum1>i) 
            while (j2+1<=len && sum2<i) {
//              if (la1[s1[j2+1]-'a']==0 && sum2==i-1) break;
                la1[s1[j2+1]-'a']++;
                if (la1[s1[j2+1]-'a']==1) sum2++;
                j2++;
            }

//          cout<<k<<" "<<i<<" "<<j1<<" "<<j2<<" ?\n";

            if (sum2==i && sum1==i) t[i]+=j1-j2+1;
            la1[s1[k]-'a']--;
            if (la1[s1[k]-'a']==0) sum2--;
////            
            la[s1[k]-'a']--;
            if (la[s1[k]-'a']==0) sum1--;
        }
    }

    cout<<check(1,len)<<"\n";

    for (int i=1;i<=26;i++)
        if (t[i]) cout<<t[i]<<"\n";
    return 0;
}