题解：CF2276E Good Substrings

· · 题解

线段树棒棒糖题。

题意

详见别人。

做法

考虑枚举左端点，考虑预处理对于一个端点，离他最近坏串端点为 A，最近好串位置为 B，这个是简单的。下面讲一下怎么求坏串数，好串就是总的减去即可。

显然如果 B<A 则以当前点为左端点一定不可能是坏串，直接枚举下一个。

若 A<B，考虑这样一件事：固定左端点为 l，只要右端点在 [A,B-1] 内，形成的一定是坏串。那么让右端点在那个区间里面，显然一定有 i\in [l,A] 都贡献 B-A+1，i \in[A,B-1] 贡献一个首项为 B-A，公差 -1 的等差数列。直接线段树维护，没了。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define DF(i,a,b) for(int i=(a);i>=(b);i--)
const int N=3e5+10;
int T,n,nx[N][10];
struct SGT{
    struct node{int v,k,d;}t[N<<2];
    #define ls p<<1
    #define rs p<<1|1
    #define pp(p) t[p].v=t[ls].v+t[rs].v
    void build(int p,int l,int r){
        t[p]={0,0,0};
        if(l==r)return;
        int mid=(l+r)>>1;
        build(ls,l,mid);build(rs,mid+1,r);
    }
    void pd(int p,int l,int r){
        int&k=t[p].k,&d=t[p].d,mid=(l+r)>>1;
        if(!k&&!d)return;
        int ll=mid-l+1,lr=r-mid,kr=k+ll*d;
        t[ls].v+=ll*k+ll*(ll-1)*d/2;
        t[ls].k+=k,t[ls].d+=d;
        t[rs].v+=lr*kr+lr*(lr-1)*d/2;
        t[rs].k+=kr,t[rs].d+=d,k=d=0;
    }
    void update(int p,int l,int r,int ql,int qr,int k,int d){
        if(qr<l||r<ql||ql>qr)return;
        if(ql<=l&&r<=qr){
            t[p].v+=(r-l+1)*(k+(l-ql)*d)+(r-l)*(r-l-1)*d/2;
            t[p].k+=k+(l-ql)*d,t[p].d+=d;
            return;
        }
        int mid=(l+r)>>1;pd(p,l,r);
        if(ql<=mid)update(ls,l,mid,ql,qr,k,d);
        if(qr>mid)update(rs,mid+1,r,ql,qr,k,d);
        pp(p);
    }
    int query(int p,int l,int r,int pos){
        if(l==r)return t[p].v;
        int mid=(l+r)>>1;pd(p,l,r);
        if(pos<=mid)return query(ls,l,mid,pos);
        else return query(rs,mid+1,r,pos);
    }
}t;
int get(int l,string s){
    for(char c:s){
        l=nx[l][c-'0'];
        if(l==n+1)return l;
        l++;
    }
    return l-1;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        F(j,0,9)F(i,1,n+1)nx[i][j]=n+1;
        string s;cin>>s;s=" "+s;t.build(1,1,n);
        DF(i,n,1){
            nx[i][s[i]-'0']=i;
            F(j,0,9)nx[i][j]=min(nx[i][j],nx[i+1][j]);
        }
        F(l,1,n){
            int A=get(l,"2025"),B=get(l,"2026")-1;
            if(B<A)continue;
            t.update(1,1,n,l,A,B-A+1,0);t.update(1,1,n,A+1,B,B-A,-1);
        }
        F(i,1,n)cout<<((n-i+1)*i-t.query(1,1,n,i))<<" ";
        cout<<"\n";
    }
    return 0;
}