总结
输在语文上了。
t1 签到题。
t2 神秘 dp，问题主要在处理二次函数的限制上，考虑直接拆开或者差分后面的思路就容易了。
t3 语文题，要将集合的关系转移到图上，部分分给了非常多的正解启示。
t4 dp，卡特兰数，格路计数。
题解
road
二分答案，转化为最少添加几个传送锚点，对于每两个点对计算需要添加多少个传送锚点，然后跑最短路即可。
时间复杂度为 \(\mathcal O(m^2\log n)\)。
seq
对于 \(50\) 的部分分，令 \(dp_{i,j}\) 为前 \(i\) 个数，结尾为 \(j\) 的最小花费，暴力转移即可。时间复杂度为 \(\mathcal O(nA^2)\)。
对于 \(70\) 的部分分，考虑如何不用枚举前一个数的大小。因为 \(c\) 是固定的，所以 \(dp_{i-1,j}\rightarrow dp_{i,k}\) 的花费为 \(c\times|j-k|\)。
于是记录 \(sum_{i,j}\) 表示 \(\min(dp_{i,k}+c\times(k-j))\)，正着反着扫一遍预处理，就可以做到 \(\mathcal O(1)\) 转移。
需要滚动数组避免空间爆炸，时间复杂度为 \(\mathcal o(nA)\)。
对于全分，发现对于左右两边都比自己大的数，肯定会不停往上增加，直到 \(x^2>2c\)。
但在那之前，如果它与左右两边某一个数一样大了，那么两个数一定会一起向上增加或是一起停止，否则无贡献甚至负贡献。
\(x^2\) 的限制非常烦人，考虑拆开。因为 \((x+1)^2-x^2=2x+1\)，所以只用维护 \(\sum x\)。
找到 \([l,r]\) 的最大值 \(a[mid]\) ，然后拆成左右两个区间，递归去做。如果左右两个区间都能升到和 \(a[mid]\) 一样的大小，那么就把这个区间看成一个整体继续向上加，否则继续向上加是没有意义的。二分计算即可。
时间复杂度为 \(\mathcal O(n\log n)\)。
set
对于 \(c_i=1\) 的部分，如果把每个集合的下标与需要交起来的的集合下标连边，发现最后会形成森林。
建立一个根节点把他们拼成一棵树。那么集合 \(B_i\) 就是节点 \(i\) 到根节点路上所有的数组成的集合。
所以每次询问只找到这些关键点所在的最小联通块，统计出所有点到根节点路径的并即可。
这个只需要将关键点按照 dfn 排序后求所有点的深度和减去相邻两个点的 LCA 深度和。
对于 \(k\leq 2\) 的部分，还是把每个集合的下标与需要交起来的的集合下标连边。
如果 \(x\in B\)，那么从节点 \(i\) 出发，走到终点的所有路径都要经过点 \(x\)。根据这点我们建立支配树就好了。
结合上面两个部分分，正解其实就是在建好的支配树上用 \(c_i=1\) 的部分分做法计算就好了。
时间复杂度为 \(\mathcal O(n\log n)\)。
sort
考虑 dp 出合法的方案数。
从大到小插入元素，一个元素插入后作为不合法的末端，当且仅当前面两个比它大的元素中间夹了一个比它小的。
那么也就是插入到一个地方就保证这个位置前面已经插入的所有元素中间不能再插入元素了。
设 \(f_{i,j}\) 表示插了 \(i\) 个数，有 \(j\) 块（块之间可以插元素）的方案数。
转移枚举插在哪个空隙，发现插在最开头和前两个块中间会使块数加一，其它的会使 \(j\) 块变成 \(2\leq k\leq j\) 块。
转移就是 \(2f_{i,j}\to f_{i+1,j+1}\) 和 \(f_{i,j}\to f_{i,k}(2\leq k\leq j)\)。直接写是 \(\mathcal O(n^3)\) 的。
优化成 \(\mathcal O(n^2)\)，有 \(f_{i,j} = f_{i,j+1} + 2f_{i-1,j-1} + f_{i-1,j}\)。
转化成格路计数，即为：
\[\left| L\left((0,0)\to(n,n)\mid x\geq y\right)\right|,(x,y)\to (x+1,y),(x,y+1),(x+1,y+1) \]可分治 FFT / oeis 法做。时间复杂度为 \(\mathcal O(n\log n)\) 到 \(O(n)\) 不等。
标签：8.5,log,复杂度,leq,模拟,集合,mathcal,dp From： https://www.cnblogs.com/QcpyWcpyQ/p/18343999