UOJ NOI Round #1
A. 争夺圣杯
10
$n \le 10^2$
暴力枚举所有区间求出最大值计算答案。
时间复杂度 $\mathcal O(n^3)$。
30
$n \le 10^3$
$\max \{ a_l, a_{l + 1}, \cdots, a_r \} = \max \{ \max \{ a_l, a_{l + 1}, \cdots, a_{r - 1} \}, a_r \}$，先枚举 $l$，然后升序枚举 $r$ 更新最大值。
时间复杂度 $\mathcal O(n^2)$。
90
$n \le 5 \times 10^5$
暴力做法已经没有什么可以优化的地方了，把它扔进垃圾桶。
考虑一个元素 $a_x$ 在哪些区间中会成为最大值。
找到 $a_x$ 之前第一个比 $a_x$ 大的元素 $a_L$，若没有则 $L = 0$。
找到 $a_x$ 之后第一个比 $a_x$ 大的元素 $a_R$，若没有则 $R = n + 1$。
设 $p = x - L, q = R - x$，则以 $a_x$ 为最大值的区间一共有 $pq$ 个。
观察这些区间的长度分布，不妨设 $p \le q$，考虑长度 $len$：
- 当 $1 \le len \le p$ 时，长度为 $len$ 的区间共有 $len$ 个。
- 当 $p \lt len \le q$ 时，长度为 $len$ 的区间共有 $p$ 个。
- 当 $q \lt len \le p + q - 1$时，长度为 $len$ 的区间共有 $p + q - len$ 个。
这三段都是关于 $len$ 的等差数列。
所以相当于给一个数组加上若干等差数列，只要求最后每个位置的答案，直接在这个数组的一阶和二阶差分上进行修改，最后从前往后扫一遍求出原数组即可。
使用倍增 RMQ 建出笛卡尔树来计算 $L, R$。
时间复杂度 $\mathcal O(n \log n)$。
100
其实并不需要建出笛卡尔树，只要使用两个单调队列从前往后和从后往前分别扫一遍，就能对每个位置求出对应的 $L, R$。
时间复杂度 $\mathcal O(n)$。
B. 合唱队形
30
$n \le 30$
$m \le 30$
$n = m$
最终状态只有一个，每一个人都必须学会一个特定的音。
相当于有 $n$ 个数，每一次等概率看一个数再放回去，问期望多少步看到特定的 $k$ 个数。
考虑从看过 $i$ 个经过若干次观看到达看过 $i + 1$ 个，那么每一次看一个数都有 $\frac{k - i}{n}$ 的概率完成转移，因此这一步的期望步数就是 $\frac{n}{k - i}$。
答案为 $\sum_{i = 1}^k \frac{n}{k - i + 1}$。
60
$n \le 5$
$m \le 5$ $t_i$ 的长度不超过 $3$
总状态数不超过 $2^{15}$，直接列方程高斯消元求答案还是是无法接受。
考虑每一个点出发的转移，可以发现每一个点能转移到自己或者多一个已完成课程的状态，因此转移是一个套上自环的 DAG，于是就可以按照拓扑序进行 DP，对每一个点解一个一元一次方程即可。
C. 果冻运输
A. Jakarta Skyscrapers
令 $n = \max(a, b)$。
10
$a, b, c \le 400$
暴力枚举得到消息的两个 doge，看他们能不能使一个之前没有得到过消息的 doge 得到消息，直到不能操作为止。
时间复杂度 $\mathcal O(n^3)$，操作次数 $n$。
30
$b = 1$
显然如果 $c \gt a$ 则无解。
否则可以采用类似这种方式：
$a~~~~~~~~~~~~ \ 1$
$a-1~~~~~~1$
$a~~~~~~~~~~ \ a-2$
$a-2~~~~~~2$
$a~~~~~~~~~~ \ a-4$
$a-4~~~~~~4$
$\cdots$
在 $2 \log a$ 次操作内得到所有不超过 $a$ 的 $2$ 的幂，进而可以通过二进制分解在 $3 \log a$ 次操作内得到所有不超过 $a$ 的数。
50
$c = 1$
显然如果 $\gcd(a, b) \gt 1$ 则无解。
否则可以采用辗转相除的方法得到 $1$。
每次计算 $x \bmod y = x - \lfloor \frac{x}{y} \rfloor \times y$ 时，采用类似算法二的做法得到 $\lfloor \frac{x}{y} \rfloor \times y$。
这样看起来是 $3 \log^2 n$ 次的，但其实每次的 $\frac{x}{y}$ 的乘积不会超过 $n$，所以这些 $3 \log \frac{x}{y}$ 之和也不会超过 $3 \log n$。
100
$a, b, c \le 10^{18}$
特判 $c \gt \max(a, b)$ 和 $c \bmod \gcd(a, b) \neq 0$ 两种无解情况。
将算法二和算法三结合，先通过算法二得到 $\gcd(a, b)$，再通过算法三得到 $c$。
操作次数不超过 $6 \log n$。
B. 奇怪的线段树
15
$n \le 10$
一共有 $2 n - 1$ 个节点，可以直接状压这些节点的颜色，每一次枚举一个区间放上去进行转移。
时间复杂度 $\mathcal O(2^{2 n - 1} n^2)$。
30
$n \le 20$
不难发现无解当且仅当存在一个节点它的孩子中有黑色节点但它自己却是白色的，只要不存在这样的情况，可以直接找出所有是黑色但是孩子都不是黑色的节点，仅对这些节点的区间单独操作，这样就得到了一个可行解，因此这个条件是充分必要的。
于是就不用状压全部节点了，只需要考虑所有是黑色但是孩子不是黑色的节点的染色情况就行了，这样状态数就减少到了 $\mathcal O(2^n)$，实际上算法一种的有用状态也就只有这么多。
时间复杂度为 $\mathcal O(2^n n^2)$。
60
$n \le 50$
80
$n \le 200$
把每一个点的后继都连出来：
- 对于每一个右儿子 $i$，它能走到所有 $l_j = r_i + 1$ 的节点。
- 对于每一个左儿子 $i$，它能走到所有 $l_j = r_i + 1$ 的左儿子。
把这张图建出来，不难发现得到了一个 DAG，因为我们每走一步所在节点的左端点都是增加的。
同时不难发现这个 DAG 上的每一条路径都是合法的，即都是满足由连续的一段右儿子和连续的一段左儿子组成的，因此这个 DAG 上的每一条路径，都可以通过一次操作进行覆盖。
于是问题转化成给出一个 DAG，其中有一些点至少经过一次，有一些点不能经过，问最少多少条路径能满足条件。
这是一个裸的下界最小流问题。
点数 $\mathcal O(n)$，边数 $\mathcal O(n^2)$，流量 $\mathcal O(n)$，时间复杂度 $\mathcal O(n^3)$。
100
$n \le 4000$
考虑优化连边，连边的瓶颈在于对每一个右儿子都连一条边指向与它相邻的节点，这部分是可以优化的。
新建 $n$ 个辅助节点，对于每一个右儿子 $[l_i, r_i]$，都连一条边指向第 $r_i + 1$ 个辅助节点。
同时对每一个线段树节点 $[l_i, r_i]$，都从第 $l_i$ 个辅助节点连一条边回来。
这样边数就优化到了 $\mathcal O(n)$，时间复杂度 $\mathcal O(n^2)$。
C. 火车管理
30
$n, m \le 10^3$
使用 std::vector 模拟栈。
时间复杂度 $\mathcal O(n^2)$，空间复杂度 $\mathcal O(n^2)$。
100
$n, m \le 5 \times 10^5$
建立一颗可持久化线段树，维护每个铁路每个时间的栈顶的吨位和栈顶火车的入栈时间。
维护一颗线段树用来统计答案。
于是操作就显得很简单了：
- 区间询问：直接在答案线段树里询问即可。
- 区间压数：在可持久化线段树上进行区间覆盖，这个是十分基础的数据结构技巧，然后在答案线段树上修改一下。
- 区间弹数：由于我们记录了入栈时间，所以我们删完后用可持久化线段树查出当前入栈之前的栈顶的信息即可，然后在答案线段树上和可持久化线段树上修改一下。
时间复杂度 $\mathcal O(n \log n)$，空间复杂度 $\mathcal O(n \log n)$。