NOIP 模拟赛（三十五）
Problem A: 牛堡的十字路口
给定每条街道（南北向，东西向）和经过速度，求到每个交叉口的最短时间。
$10^5$
一种很自然的想法是暴力连边，跑最短路，但你不会发现从原点到目标点是一次函数，然后就是斜率优化 DP。
设 $(i,j)$ 为第 $i$ 行第 $j$ 列的位置。
考虑 dijkstra 求单源最短路的过程（相同权值优先行小的位置），发现每次扩展后已经处理好的点在每一列上一定是从 $(1,j)$ 到 $(i,j)$ 的一段区间，所以从起点 $(1,1)$ 到 $(i,j)$ 的最短路径一定是 $(1,1)\to(1,k)\to(i,k)\to(i,j)$；
而如果只从编号小的列走到编号大的列的情况下横向移动的权值固定，所以可以将 $t_i$ 变为 $t_i$ 的前缀 min 而不影响答案，而最后一列每个位置的最短路径是和这个位置的行有关的一个一次函数，而走到后面又走回来相当于全部加上一个相同的贡献，那么其实就是要考虑一堆一次函数求一个上凸壳，发现列越大，这个一次函数的斜率是不增，那么斜率优化即可
时间复杂度为 $O((n+m)\log n)$
Problem C: Squirrel Migration
给你一个 $n$ 个结点的树，询问有多少个 $1\dots n$ 的排列 $p$ 满足 $\sum_{i=1}^n dis(i,p_i)$ 最大。其中 $dis(x,y)$ 表示树上 $x\to y$ 的路径经过的边数。
考察每条边的贡献。
设切掉这个边后形成连通块 $s_1,s_2$，设 $|s_1|≤|s_2|$，那么这条边的贡献 $≤2|s_1|$，取等当且仅当 $s_1$ 中的每个点 $x$，$px∈s_2$。
取重心为根，那么每个子树大小均不大于其补树大小，也就是说每个子树都是 $s_1$，这个子树中的每个点都要连向其补树。
考虑容斥：
对于一个大小为 $x$ 的子树，钦定其中有 $i$ 个点不合法，那么显然是 $\dbinom x i ^2 i!$。
钦定 $i$ 个点乘上钦定 $i$ 个 $p$ 乘上交换顺序。
那么可以算出重心每个子树的有 $i$ 个点不合法的数量，考虑合并到重心。树形背包即可。
然后对于根，你合并出一个 $f_i$ 表示有 $i$ 个点不合法的数量，那么答案就是 $\sum_{i=0}^n f_i(n-i)!(-1)^i$。
注意到这里的时间复杂度 $O(n^2)$，瓶颈在于树形背包。
这里树形背包的形式相当于将若干个总长为 $n$ 的多项式相乘。我们每次选择两个长度最小的多项式用 $\text{NTT}$ 相乘（哈夫曼树），即可做到 $O(n\log^2n)$ 的时间复杂度。
原题数据范围 $n \le 5000$，改之后 $n \le 10^5$，强行让你用多项式、
NOIP 模拟赛（三十四）
Problem A: 归并
给定排列 $a$，$m$ 次操作：
$1\ l\ x\ r$ 将 $a_{l \sim r}$ 改为 $\text {merge}(a_{l \sim x},a_{x+1 \sim r})$（归并）；
$2\ x$ 询问 $a_x$。
其中 $\text{merge}$ 实现：
def merge(a, b):
c=[]
while a.size() and b.size():
if a[0]<b[0]:
c.append(a[0])
a.pop_front()
else:
c.append(b[0])
b.pop_front()
return c+a+b
33 pts 做法直接用栈模拟；
正解：将归并转化，平衡树维护。
直接用 FHQ_Treap，注意按 size 合并和按 val 合并。
void solve(int l, int m, int r) {
int a, b, c, d, e, f;
split_siz(rt, l - 1, a, b);
split_siz(b, m - l + 1, b, c);
split_siz(c, r - m, c, d);
rt = a;
while (b && c) {
int cur1 = find(b);
int cur2 = find(c);
if (cur1 > cur2) swap(cur1, cur2), swap(b, c);
split_val(b, cur2, e, b);
rt = merge(rt, e);
}
if (c) rt = merge(rt, c);
rt = merge(rt, d);
}
Problem B: Cigar Box
对于一个序列 ${1,2,3,\dots,n}$ 删除任意一个数，将它加到这个序列的开头或末尾，转化为 $a$ 的方案数。
首先考虑对于最后一个数，只有最后一次操作才会对他有意义，所以每个数只保留最后一次操作，得到长度为 $k$ 的简化操作序列，
这些操作可以随意插到最后一次操作前面，
对简化操作序列计数，那方案数为：$\left(^{l-1+n-r}_{l-1}\right)$
Problem C: Wine Thief
一个合法的子序列定义为：
长度为 $m$
在原序列中没有连续 $2$ 个元素同时在子序列中，不存在 $p_i+1=p_{i+1}$
定义一个“成功”子序列的权值为 $\sum a_{p_i}$，求出所有合法的子序列的权值和 $\bmod\ 998244353$