https://codeforces.com/contest/1428/problem/F
vp的时候没想出来。。。主要D想太久了，其实F也不太会
这题的关键是想到对于一个确定的r，l越左高度f(l,r)越高
于是就能想到每次r向右拓展一格，如果是1个新的1，那么左边就有一部分要全增加1
于是一个很简单想法就是在线段树上二分找到覆盖到哪里，然后区间覆盖，然后求个前缀和就是这个当前r对应的所有f(l,r)之和
然而这样十分难写
于是我们发现每次增加只增加1，且我们可以考虑对当前末尾最长的连续的1，[l,r]，这一段是全部要+1的，然后l左边的就尝试用r-l+1去覆盖他们，我们就可以用rid[i]表示高度为i的最右边的端点在哪，每次r新增一个1，就把rid[r-l+1]=l，然更新一下总和就行了，[l+1,r]这一段是一个等差数列可以直接算，当s[r+1]='0'时，再更新一下rid[1]-rid[r-l+1]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxl=5e5+10;int n,m,cnt,tot,cas;ll ans;
int a[maxl];ll rid[maxl];
bool vis[maxl];
char s[maxl];inline void prework()
{scanf("%d",&n);scanf("%s",s+1);
}inline void mainwork()
{ll tmp=0,l=1,r;ans=0;for(int i=1;i<=n;i++)if(s[i]=='0')ans+=tmp,l=i+1,rid[0]=i;else{r=i;tmp-=(rid[r-l]-rid[r-l+1])*(r-l);tmp+=(l-rid[r-l+1])*(r-l+1);rid[r-l+1]=l;tmp+=r-l;ans+=tmp; if(s[i+1]!='1' && i+1<=n){for(int j=1;j<=r-l;j++)rid[j]=r-j+1;}}
}inline void print()
{printf("%lld",ans);
}int main()
{int t=1;//scanf("%d",&t);for(cas=1;cas<=t;cas++){prework();mainwork();print();}return 0;
}