T1
SPFA 就能过！给我震惊到了。
可以斜率优化。对每个站点维护一个凸包。
\[f(x)=Ax^2+Bx+C\\ dp_{v,q}=\min_{i=0}^{p}\{dp_{u,i}+f(p-i)\}\\ (i,dp_{x,i}+Ai^2-Bi) \]T2
考场想了想区间 dp，有点思路但是时间不多了有点慌，打个暴搜直接跑。
相当于将位置当作第二关键字比较，最大的数将区间划分成两段互不影响的区间。可以区间 dp，设 \(dp_{l,r,k}\) 表示 \(l-r\) 中最大值为 \(k\) 的方案数，那么有状态转移方程：
\[dp_{l,r,k}=\sum_{mid}dp_{l,mid-1,k}\times dp_{mid+1,r,k-1} \]复杂度优化以下可以达到 \(O(nmw)\) （\(w\) 为值域）。但 \(10^9\) 的值域是接受不了的。
如果将 \(l=r\) 时的 \(dp_{l,r,k}\) 看成是关于 \(k\) 的函数，那么很明显是一次的。再观察转移方程，发现区间 \([l,r]\) 的 dp 值是关于 \(k\) 的 \(r-l+1\) 次多项式。那么对于每一个区间可以按原来的方法求出 \(dp_{l,r}\) 前 \(n+1\) 项的值，用拉格朗日插值法求出后面的值。
T3
考场打的二维线段树优化建图，第一遍打，但是很快就打完了。回头看一眼——妈呀这得 MLE 飞，去掉了一些连边，最后还是只有 \(64\)。对 K-D Tree 不太熟，想不到。
K-D Tree 优化建图。按照正常的建图思路会爆掉，可以不实际连边，在 K-D Tree 上维护整棵树没有松弛过的点的最小值及其位置。每次从最小值处松弛。每个点只会被松弛 \(1\) 次。时间复杂度 \(O(n\log n+m\sqrt n)\)。
标签：20230707,Tree,mid,暑期,建图,区间,优化,集训,dp From： https://www.cnblogs.com/dks-and-xiao-yu/p/17536017.html