[Ynoi2015]Day1题解

Idea：lxl Solution：lxl Std：lxl Data：lxl

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

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

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

对这题的评价：1/11

Idea：ccz Solution：ccz Std：ccz Data：ccz

如果一个位置 $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

Idea：lxl Solution：lxl Std：lxl Data：lxl

设我们需要输出长 $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

OldDriverTree的博客