「Summary」2022-08-01 做题记录

甚么玩意（

2022-08-01

训练

$\mathbb{CF95D}$

怎么调了这么久🤮

定义 $dp_{pos, dist, flag}$ 为当前位是从高到低的第
$pos$ 位，此时离上一个的距离为 $k + 1 - dist$ ，$flag$ 表示是否已经有匹配成功的两个数字。

$\mathbb{AtCoder \ Beginner \ Contest \ 248}$

$\mathbb{Ex}$

着实被教育了

有两种解法，都写写。

$\mathbb{分治}$

设 $sol(l, r)$ 为 $[l, r]$ 内合法的子区间的个数，则 $sol(l, r) = sol(l, mid) + sol(mid + 1, r) + f$ ，其中 $f$ 表示左端点在 $[l, mid]$ 而右端点在 $[mid + 1,r]$ 的合法区间个数。
则求出 $f$ 问题解决了，可以大力分类讨论。

• 最大值和最小值都在左侧
• 最大值和最小值都在右侧
• 最大值在左侧，最小值在右侧
• 最大值在右侧，最小值在左侧