admin管理员组文章数量:1584341
题目链接
题意:有由字符集{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;
}
本文标签: 线段RoundsControversialCF
版权声明:本文标题:Controversial Rounds【CF-1398 F】【线段树】 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1727942503a1139054.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论