题目概述

CF1428F

解题报告

不是很难，但是要考虑的周全一些。

对于一块连续的 $1$（假设区间是 $[L,R]$ ），我们枚举 $[L,i](i>L)$ 和 $[j,R](j<R)$ 。

对于 $[L,i]$ ，如果想作为最大块产生贡献，那么显然不能向右扩展，只能向左扩展，且最远扩展到第一个比 $[L,i]$ 多的块之前。对于 $[j,R]$ 和整个块 $[L,R]$ 同理。

但是我们发现这样会统计重复，因此我们向左扩展时，强制最远扩展到第一个不少于 $[L,i]$ 的块之前，这样就避免左右扩展时统计重复。

还有一个容易忽略的情况，如果对于连续 $1$ 的区间 $[l,r]$ ，$l-1$ 和 $r+1$ 都是 $1$ ，说明 $[l,r]$ 不能向左向右扩展，但是也需要统计。

向左向右扩展利用数据结构就行了，比如二分+ST表。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=500000,LOG=19;

int n,LS[maxn+5],RS[maxn+5];char s[maxn+5];
int RMQ[2][maxn+5][LOG+1],lg[maxn+5];LL ans;

int Max(int ID,int L,int R) {int k=lg[R-L+1];return max(RMQ[ID][L][k],RMQ[ID][R-(1<<k)+1][k]);}
int FindL(int l,int r,int x){
    int L=1,R=r-l+1;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        Max(1,r-mid+1,r)<=x?L=mid+1:R=mid-1;
    return r-R+1;
}
int FindR(int l,int r,int x){
    int L=1,R=r-l+1;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        Max(0,l,l+mid-1)<=x?L=mid+1:R=mid-1;
    return l+R-1;
}
int main(){
    scanf("%d%s",&n,s+1);
    for (int i=1;i<=n;i++) if (s[i]=='1') LS[i]=LS[i-1]+1; else LS[i]=0;
    for (int i=n;i>=1;i--) if (s[i]=='1') RS[i]=RS[i+1]+1; else RS[i]=0;
    for (int i=1;i<=n;i++) RMQ[0][i][0]=LS[i],RMQ[1][i][0]=RS[i];
    for (int j=1;(1<<j)<=n;j++)
        for (int i=1;i+(1<<j)-1<=n;i++)
            RMQ[0][i][j]=max(RMQ[0][i][j-1],RMQ[0][i+(1<<j-1)][j-1]),
            RMQ[1][i][j]=max(RMQ[1][i][j-1],RMQ[1][i+(1<<j-1)][j-1]);
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for (int i=1;i<=n;i++)
        if (s[i]=='1'){
            int j=i-LS[i]+1,L=FindL(1,j-1,LS[i]-1),R=FindR(i+1,n,LS[i]);
            ans+=(LL)(j-L+1)*(R-i+1)*LS[i];
            if (s[i-1]=='1'){
                j=i+RS[i]-1;R=FindR(j+1,n,RS[i]);
                ans+=(LL)(R-j+1)*RS[i];
            }
        }
    for (int i=1;i<=n;i++)
        if (s[i-1]!='1' && s[i]=='1' && RS[i]>=3)
            for (int j=1;j<=RS[i]-2;j++)
                ans+=(LL)(RS[i]-2-j+1)*j;
    printf("%lld\n",ans);return 0;
}