T1 第负一题
第负一题（×）
地府一题（√）
当时觉得是唯一可做题目，然后伪了。
这道题其实 20pts 很好拿，就是设计 \(f_{i,[0/1]}\) 表示 \(i\) 表示第几轮，\(0/1\) 表示取或不取：
然后这个是 \(O(n)\) 的，套上枚举的长度和起点就是 \(O(n^3)\)。
然后考虑分治（？怎么想到分治的？）以中点 \(mid\) 分界，设：
-
\(lf_{i,[0/1],[0/1]}\) 表示现在到第 \(i\) 轮，第一个 \(0/1\) 表示是否选 \(mid\)，第二个 \(0/1\) 表示是否选择第 \(i\) 个元素。
-
\(rf_{i,[0/1],[0/1]}\) 表示现在到第 \(i\) 轮，第一个 \(0/1\) 表示是否选 \(mid+1\)，第二个 \(0/1\) 表示是否选择第 \(i\) 个元素。
为了简单表示，我们这样写：
-
\(lg_{i,[0/1]}\) 是向左，\(1\) 表示选 \(mid\)，\(0\) 表示不选 \(mid\) 的最大值，即 \(max(lf_{i,[0/1],0},lf_{i,[0/1],1})\)。
-
\(rg_{i,[0/1]}\) 是向右，\(1\) 表示选 \(mid+1\)，\(0\) 表示不选 \(mid+1\) 的最大值，即 \(max(rf_{i,[0/1],0},rf_{i,[0/1],1})\)。
对于区间 \([l,r]\)，因此就有：
对于 \(lg\) 和 \(rg\)，第二维的 \([0,1]\) 只可能是 \((0,0)\)，\((0,1)\)，\((1,0)\)，因为 \(mid\) 与 \(mid+1\) 相邻。
即：
然后我们发现 \(max()\) 这里面三种方案 \((0,0),(0,1),(1,0)\) 都与 \((0,0)\) 存在交集。
然后对他进行一个优雅的转化：
于是现在我们设 \(fl_i=max(lg_{i,1}-lg_{i,0},0),fr_i=max(rg_{i,1}-rg_{i,0},0)\)，原本的式子就被转化：
如何实现代码？
不会求教。