题目链接
题意：有由字符集{0，1，?}构成的长度为N的字符串，知道"?"可以变成0、1中的任意一个数，现在问长度为1到N的最多0、1连续段的个数。
很显然一点，如果我们直接跑N次，假设查询可以O(1)的完成，那么时间复杂度是一个调和级数，也就是级别的，但是很显然我们需要查询这样的一个东西。
现在需要有这样的一个操作：查询区间内第一个出现的连续长度大于等于i的连续段的首地址，那么，我们不妨维护这样的一个线段树，记录每个位置的最远连续长度，那么实际上就是找到区间范围内第一次出现的长度大于等于i的点的位置。
总时间复杂度。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e6 + 7;
int N;
char s[maxN];
namespace Segement
{int tree[maxN << 2] = {0}, nex_len[maxN];void build(int rt, int l, int r){if(l == r){tree[rt] = nex_len[l];return;}int mid = HalF;build(Lson);build(Rson);tree[rt] = max(tree[lsn], tree[rsn]);}int query(int rt, int l, int r, int ql, int qr, int qval){if(ql > qr) return -1;if(tree[rt] < qval) return -1;if(l == r) return l;int mid = HalF;if(ql <= l && qr >= r){int ans = query(QL, qval);if(~ans) return ans;ans = query(QR, qval);return ans;}if(qr <= mid) return query(QL, qval);else if(ql > mid) return query(QR, qval);else{int ans = query(QL, qval);if(~ans) return ans;else return query(QR, qval);}}
};
using namespace Segement;
int main()
{scanf("%d", &N);scanf("%s", s + 1);nex_len[N] = 1;int sum = s[N] == '?' ? 1 : 0;char old = s[N];for(int i=N - 1; i>=1; i--){if(s[i] == s[i + 1]){nex_len[i] = nex_len[i + 1] + 1;if(s[i] ^ '?') sum = 0;else sum++;}else if(s[i] == '?'){nex_len[i] = nex_len[i + 1] + 1;sum++;}else if(s[i + 1] == '?' && (s[i] == old || old == '?')){nex_len[i] = nex_len[i + 1] + 1;sum = 0;old = s[i];}else{nex_len[i] = 1 + sum;sum = 0;old = s[i];}}build(1, 1, N);printf("%d", N);for(int i=2, pos, beg_pos, end_pos, ans, tmp; i<=N; i++){if(tree[1] < i){printf(" 0");}else{ans = 0;pos = 1;beg_pos = query(1, 1, N, pos, N, i);while(~beg_pos){end_pos = beg_pos + nex_len[beg_pos] - 1;tmp = nex_len[beg_pos] / i;ans += tmp;pos = beg_pos + tmp * i;beg_pos = query(1, 1, N, pos, N, i);}printf(" %d", ans);}}printf("\n");return 0;
}