第一问显然是一个很简单的 $DP$ ，但是第二问和第三问就要用最大流来求了，怎么求呢？

首先我们 $DP$ 出来的 $f$ 数组，$f[i]$ 表示以i结尾的最长不下降子序列的长度 ，然后就是网络流的连边了。首先因为一个点只能经过两次，我们需要将其拆为入点和出点，中间连的边的边权自然是 $1$ ，然后对于一个 $i$ ，如果 $f[i]$ 等于最长长度($s$)，那么很显然这个 $i$ 就可以给答案做出一个贡献，这个时候 $i$ 的出点向 $t$ 连一条边权为 $1$ 边。

又是一个神奇的数据结构……

$K$-$D \ Tree$ 中 $D$ 是维度($Dimension$)的缩写，所以 $K$-$D \ Tree$ 的实际意思就是 $K$ 维树。当然 $K$-$D \ Tree $ 一般用于维护二维平面上的信息，所以我们平常用的 $K$-$D\ Tree$ 又叫 $2$-$D \ Tree$ 。

我们一起来推一推。

设 $f[i][j]$ 表示：现在是第 $i$ 天，手上拥有的股票数为 $j$ 时赚到的最多的钱

我们考虑转移几个方向：空手买，不买不卖，之前买过了现在继续买，买过后需要卖

前置芝士：网络流-最大权闭合子图

定义：对于一个图的子图，当且仅当这个子图中的任意一点都不会与该子图外的点联通时，称这个子图为该图的闭合子图。在该图所有的闭合子图中，点权和最大的那个我们称作最大权闭合子图。

$KDT$ 大法好！

直接建 $KDT$ 维护一下所有的可能存在玩偶的结点，该插入的时候插入，查询的时候只需要沿着 $KDT$ 往下走，然后随时对 $ans$ 取 $min$ 即可。

首先可以发现，刷水题跟打伤害是可以分开处理的。

我们先用 $DP$ 预处理出能打伤害的最大天数，其余的天数都只能用刷水题的方式恢复。

于是设 $dp[i][j]$ 表示前 $i$ 天，信心值还剩 $j$ 的能够打伤害的最大天数。

回滚莫队板子题，在此不再赘述。

关于回滚莫队的文章戳这 $QwQ$ :[算法]浅谈4种莫队及例题

首先再来讲明一下题意：

给定一个长度为 $n$ 的环，环上的每个点有一个权值 $T_i$ ，要求你从环上选中任意一个点为起点开始，每个时间可以顺时钟到下一个点，或者停留不动。对于一个点，如果到这个点的时间大于等于了 $T_i$ ，那么这个点将被标记，问最少什么时候可以让所有物品都被标记。

可以发现，这个问题的答案跟以下问题的答案是等价的：

$Spaly​$ 是不会用的，这辈子也不会用的。

这道题当然可以用 $Splay​$ 做，然而不会。

于是考虑怎么来做这道题，我们先来观察一下所有的操作：

题目背景有些……………
通过题目我们可以知道最终我们要求的式子就是：

于是我们将式子拆开：