UOJ Logo OldDriverTree的博客

博客

[Ynoi2015]Day1题解

2019-10-28 09:58:08 By OldDriverTree

T1:ただいま帰りました(Version3)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5068

考虑对每个点维护$n$个bitset,$f[i][j]$表示距离这个点小于等于j的点数

可以通过BFS来处理出这些bitset,每次查询的时候把一些bitset or起来就可以了

总时间复杂度$O( nm + { n \sum a } / w )$,空间复杂度$O( n^3/w )$,可以通过压位BFS来改进BFS的时间

对这题的评价:1/11

T2:いずれその陽は落ちるとしても(Version?)

Idea:ccz Solution:ccz Std:ccz Data:ccz

https://www.luogu.org/problem/P5069

如果一个位置 $x$ 是极大值(即 $a[x-1] < a[x] \ge a[x+1]$ ),那么 $x-1$ 和 $x+1$ 不会有机会成为最大值,且 $x$ 会成为最大值 $a[x]$ 次,此时可以把 $a[x-1]$ 和 $a[x+1]$ 直接设为 $0$ 而不影响答案

将 $a[x-1]$ 和 $a[x+1]$ 设为 $0$ 后可能会出现新的极大值,最终整个序列所有非 $0$ 位置都为极大值,非 $0$位置的值之和即为所求答案

分析以上找极大值的过程可知,实际上是从每个初始极大值开始向两侧隔一个位置取一个位置,直到遇到极小值($a[x-1] \ge a[x] < a[x+1]$)或边界($x=1$ 或 $x=n$)为止,一个极小值当且仅当在和两侧极大值距离均为偶数时会成为极大值

于是可以用数据结构维护极大值、极小值以及它们之间的区间

可以用平衡树/线段树维护极大值和极小值位置构成的序列,支持插入删除查询前驱后继,用树状数组/线段树分别维护原序列奇偶位置的前缀和,支持单点修改

也可以直接用线段树维护原序列,分类讨论两个区间信息合并的每种情况。

总时间复杂度$O( n + qlogn )$,总空间复杂度$O( n )$

对这题的评价:3/11

T3:たとえ未来が見えなくても(Version3)

Idea:lxl Solution:lxl Std:lxl Data:lxl

https://www.luogu.org/problem/P5070

设我们需要输出长 $1$ 到 $k$ 的所有极长值域连续段个数

考虑扫描线,扫右端点,维护所有左端点的答案

对每个数,显然我们只需要考虑其离右端点最近的一次出现位置,记 $x$ 最近的一次出现位置为 $pos_x$

可以发现我们扫到 $x$ 位置,其值为 $a_x$ 时,我们只需要更新其对值域在 $a_x-k$ 到 $a_x+k$ 这个范围内的数的影响

我们从 $a_x$ 这个位置开始朝两边拓展,设现在的区间是 $[l,r]$ ,则每次根据 $pos_{l-1}$ 和 $pos_{r+1}$ 中离右端点最近的一个,拓展到 $l-1$ 或者 $r+1$

不失一般性设拓展到了 $[l-1,r]$ ,相当于说如果我们左端点到当前右端点的区间包含了 $pos_{l-1}$ ,则其存在一个长为 $r-(l-1)+1$ 的非极长值域连续段

显然对于 $x$ 我们最多拓展 $k$ 次,形成了一个类似阶梯的结构,于是可以处理出每个长度的值域连续段所对应的左端点的范围

维护 $k$ 个树状数组,对每个进行一次区间加操作,总共进行 $O(k)$ 次区间加操作即可

总时间复杂度 $O( (n+m)klogn )$,空间复杂度$O( n + mk/w )$

对这题的评价:4/11

评论

mrsrz
前排资瓷

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。