写笔记时发现有三道连着的题！！！顺便发出来。
JOI Open Seesaw
在一个数轴上，初始 a_1,a_2\dots a_n(a_1<a_2\dots <a_n) 的位置上有一个砝码。
每一次你可以拿走 a_1 或 a_n。
令 m_i 表示还剩 i 个砝码时的 \dfrac{\sum a_j}{i}，最小化 \max\{m_i\}-\min\{m_i\}。
结论，答案区间 $[l,r]$ 合法当且仅当对于任何长度 $i$，存在一个长度为 $i$ 的区间的 $\sum\dfrac{a_j}{i}$ 在 $[l,r]$ 之间。
如果不存在，那么一定不合法。
否则，令 $a_j$ 为长度为 $i$ ，起点为 $j$ 的区间的平均值，$b_j$ 为长度为 $i+1$，起点为 $j$ 的区间的平均值，那么一定满足：
$a_1<b_1<a_2<b_2\dots$。
那么可以通过调整，使得选的位置是可以由上一次变化而来的。
我们还知道，长度为 $n$ 的区间是一定被选的。
那么对于其他长度，可以贪心的选全局平均值在区间内的前驱后继，然后就枚举全局最小值，维护一下全局最大值。
总复杂度 $O(n\log n)$。
#### JOI Open Giraffe
给定排列 $p$，你需要构造排列 $q$，满足对于任意的一个区间 $[l,r]$，下面两个条件不能同时满足：
$1.$ 存在 $l<x<r$ 满足 $q_x>q_l,q_x>q_r$。
$2.$存在 $l<x<r$ 满足 $q_x<q_l,q_x<q_r$。
最小化 $\sum [p_i\neq q_i]$，保证 $p$ 随机生成。
$n\leq 8000$。
可以发现最大值和最小值不能同时在中间，可以递归进一个子问题。
可以把点看成 $(i,p_i)$，假若最大化 $\sum [p_i=q_i]$，那么令 $f_{l,r,x}$ 表示区间 $[l,r]$，最大值为 $x$ 的答案，相当于平面上的一个矩形，转移容易 $O(1)$。
发现最终的 $\sum[p_i=q_i]$ 不是很大，实际上是 $O(\sqrt n)$ 级别的，可以考虑 LIS+LDS。
初始我们有矩形 $((0,0),(n+1,n+1))$，做 $ans$ 次，每次尝试扩展到一个新的，尽量大的被原来矩形包含矩形，满足其中的四个角存在至少一个有点。
可以维护 $f_{i,0/1/2/3}$ 表示第 $i$ 个点四个方向的矩形边长可取的最大值，直接这样递归就是 $O(n^2\sqrt n)$ 的。
crn 的小优化是时刻只保留前 $1000$ 大的矩形。
#### JOI Open Schoolroad
给定一个带权无向图，判断 $1\sim n$ 是否存在两条长度不同的简单路。
$n,m\leq 2\times 10^5$。
先假设 $1,n$ 同在一个点双里。
我们发现，若一个不为 $1,n$ 的点的度为 $2$，那么可以直接缩掉这个点。
如果缩出了重边显然若权值相同直接删去，权值不同那么一定不合法。
若最后的图剩下了除 $1,n$ 以外的点，那么一定存在形如，$S\rightarrow x_1,x_1\rightarrow T,S\rightarrow x_2,x_2\rightarrow T,x_1\rightarrow x_2$ 的子图，这显然不合法。
不在一个点双时可能在缩的时候出现不连通。
先求出最短路 DAG，定义从 $1$ 出发的最短路 DAG 和从 $n$ 出发的最短路 DAG 的交。
假如存在从 $1\sim n$，且不在这个最短路 DAG 上的路径，那么显然存在长度不同的路，判断这个只需要一个并查集，将每条不在 DAG 上的边在并查集上连接，如果有多于两个在 DAG 上的点连通那么一定有一条路。
否则，对于每一个在这个最短路 DAG 上的点，存在 $1\rightarrow x\rightarrow n$ 的路径，那么还是项上面点双的做法。
其实这个判定就是 二端串并联图。