与 jiazhichen844和 rsy_组队

经过讨论后确定了队名：$\text{Milk Dragon Dream! It's MyGO!!}$

突然发现最后一个叹号没显示出来（，寄

我真的能在患有痴呆症的情况下在 $\text{THUPC}$ 中打出非负贡献吗？这真的可行吗？这真的能被完成吗？

我们队下午三点半才开始打试机赛

看了一下排行榜，然后决定我开 $\text{T1}$，jiazhichen844开 $\text{T2}$，rsy_开 $\text{T4}$ 和 $\text{T5}$

然后看了一下 $\text{T1}$，发现是弱智扫描线，然后在 $15:35:37$ 时过了，rsy_大佬在 $15:31:20$ 时过了 $\text{T4}$，$15:45:30$ 时过了 $\text{T5}$

但是此时 jiazhichen844还不会 $\text{T2}$，于是我们队一起开始讨论 $\text{T2}$，

最好笑的是我大胆猜测 $c$ 一定为 $0$ 或 $1$，其他人都没发现样例有一个 $c=3$ 的，而且我打了个暴力跑了几十组数据没跑出来 $c=1$ 无解的情况，并对 $c=3$ 的情况跑出了一组 $c=1$ 的答案（

$16:30$ 左右时我们队还没有一点思路，寄！

于是开 $\text{T3}$，首先对于快速求序列的值这部分通过原题机搜到了 CF1975C，并打开题解发现答案是连续三个数的中位数最大值，且这个结论在这道题也可以用（直接看题解是因为我懒得想），然后考虑一个经典的 $\text{trick}$，在所有大于序列的值的位置统计他的贡献，对于计算序列的值小于 $val$ 的方案数，发现不能有两个大于等于 $val$ 的数距离小于 $2$，于是直接 $\text{DP}$，设 $f_{x,0/1/2}$，状态含义显然，转移就根据 $val$ 和当前区间的关系，分三种情况，然后随便转移

然后考虑怎么扩展到 $l_i$ 和 $r_i$ 都很大的情况，先把所有 $l_i$ 和 $r_i$ 放到一起排序，然后对于排序后相邻的两个数构成的左开右闭区间，这区间中的每个数的与 $n$ 个区间的关系都是相同的，也就是说答案为一个不超过 $n$ 次的多项式函数，我们要算这个多项式函数在一段区间中的和，这个和显然为一个不超过 $n+1$ 次的多项式函数，于是取 $1\sim n+2$ 时函数值的前缀和，直接拉格朗日插值即可，时间复杂度 $O(Tn^3)$，在 $18:22:42$ 时过掉了 $\text{T3}$

赛后才发现我写的这个东西就是拉格朗日插值优化 $\text{DP}$，我在不知道拉格朗日插值优化 $\text{DP}$ 的情况下自己把它造出来了/jy

四道题一发罚时都没有，惊讶

试机赛结束时一共有 $11$ 个 $\text{AK}$ 的，我们队 $\text{rk}30$，希望我第二天初赛也能发挥出这样的水平吧

爆炸