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; }
