社区讨论

关于此题 push_up 的一个疑问

bbloodstalk
P2572[SCOI2010] 序列操作参与者 1已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo19lzzr
此快照首次捕获于
2023/10/22 17:27
2 年前
此快照最后确认于
2023/11/02 17:43
2 年前
查看原帖
rt，这是正解的 push_up
CPP
il void push_up(int p)
{
	tree[p].pre0 = tree[lc].sum1 ? tree[lc].pre0 : tree[lc].sum0 + tree[rc].pre0;
	tree[p].pre1 = tree[lc].sum0 ? tree[lc].pre1 : tree[lc].sum1 + tree[rc].pre1;
	tree[p].suf0 = tree[rc].sum1 ? tree[rc].suf0 : tree[rc].sum0 + tree[lc].suf0;
	tree[p].suf1 = tree[rc].sum0 ? tree[rc].suf1 : tree[rc].sum1 + tree[lc].suf1;
	tree[p].sum0 = tree[lc].sum0 + tree[rc].sum0;
	tree[p].sum1 = tree[lc].sum1 + tree[rc].sum1;
	tree[p].max0 = max(max(tree[lc].max0,tree[rc].max0),tree[lc].suf0+tree[rc].pre0);
	tree[p].max1 = max(max(tree[lc].max1,tree[rc].max1),tree[lc].suf1+tree[rc].pre1);
}
下面的是 60pts 的 push_up
CPP
il void push_up(int p)
{
	tree[p].pre0 = tree[lc].sum1 ? tree[lc].pre0 : tree[lc].len + tree[rc].pre0;
	tree[p].pre1 = tree[lc].sum0 ? tree[lc].pre1 : tree[lc].len + tree[rc].pre1;
	tree[p].suf0 = tree[rc].sum1 ? tree[rc].suf0 : tree[rc].len + tree[lc].suf0;
	tree[p].suf1 = tree[rc].sum0 ? tree[rc].suf1 : tree[rc].len + tree[lc].suf1;
	tree[p].sum0 = tree[lc].sum0 + tree[rc].sum0;
	tree[p].sum1 = tree[lc].sum1 + tree[rc].sum1;
	tree[p].max0 = max(max(tree[lc].max0,tree[rc].max0),tree[lc].suf0+tree[rc].pre0);
	tree[p].max1 = max(max(tree[lc].max1,tree[rc].max1),tree[lc].suf1+tree[rc].pre1);
}
其中，pre0/1 表示的是前缀最长连续 0/1,suf 表示的是后缀最长连续 0/1，sum0/1 表示区间内 sum0/1 的个数，max0/1 表示区间内最长连续 0/1 的个数。
这两个 push_up 的不同仅在更新 pre0/1,suf0/1里三目运算符的后半段。以第一行更新 pre0 为例，让我不理解的是，为什么如果左儿子的 sum1 为 0 时，左儿子的 len 和 sum0 不相等/yun

回复

共 4 条回复，欢迎继续交流。

正在加载回复...