传送门
题意：给你一个长度为你的由0,1，？构成的字符串，你可以选择将？改成0或1，问你构成连续i个的0或1，问你最大能构成多少个，i取1到n。
题解：首先对于每一位置维护出从当前位置往后最多能有多少个连续的0或者1，这一步分可以从前往后dp转移。考虑最暴力的做法，对于每一个i从往后长度大于i的里面选一个大于当前位置的最小id出来，如果能找到ans++，更新当前位置，否则跳出，复杂度n^2,然后考虑优化，后面寻找的过程可以用线段树来进行优化，对于后面查满足条件的最小id在线段树中实际就是大于等于当前区间的满足往后跳转的长度大于i的最小id，以最远跳转长度作为权值，进行建树，朴素情况下就是直接进入优先进入左子树查询，找到答案返回，否则进入右子树，但是这样最坏情况下需要查询线段树的所有端点，考虑优化，思想与传送门相同，记录一个最大值，单次查询为2*long，总复杂度为2*n*log在乘上一个调和级数。
AC代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
#define mid ((l+r)>>1)
#define ls k<<1
#define rs (k<<1)+1
using namespace std;
const int maxn=1e6+5;
const ll inf=1e9;
int read(){char c;int x=0,y=1;while(c=getchar(),(c<'0'||c>'9')&&c!='-');if(c=='-') y=-1;else x=c-'0';while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';return x*y;
}
int tree[maxn<<2];
int dp[2][maxn],mma[maxn];
void build(int l,int r,int k){if(l==r){tree[k]=mma[l];return ;}build(l,mid,ls),build(mid+1,r,rs);tree[k]=max(tree[ls],tree[rs]);
}
int query(int l,int r,int wi,int va,int k){if(tree[k]<va||r<wi) return -1;if(l==r) return l;int ans=-1;if(tree[ls]>=va&&mid>=wi) ans=query(l,mid,wi,va,ls);if(ans!=-1) return ans;if(tree[rs]>=va&&r>=wi) ans=query(mid+1,r,wi,va,rs);return ans;
}
char s[maxn];
int main( ){int n=read();scanf("%s",s+1);dp[0][n+1]=dp[1][n+1]=0;for(int a=n;a>=1;a--){if(s[a]=='?') dp[0][a]=dp[0][a+1]+1,dp[1][a]=dp[1][a+1]+1;else{if(s[a]=='0') dp[0][a]=dp[0][a+1]+1,dp[1][a]=0;else dp[0][a]=0,dp[1][a]=dp[1][a+1]+1;}mma[a]=max(dp[0][a],dp[1][a]);}build(1,n,1);printf("%d",n);for(int a=2;a<=n;a++){int ans=0,id=1;while(id<n){int id2=query(1,n,id,a,1);if(id2==-1) break;id=id2+a;ans++;}printf(" %d",ans);}printf("\n");
}