- 搬题人：
- 咖啡, 画图：Qingyu
- 治病, 拓扑序计数：feecle6418
- 序列：Wu_Ren
- 水果：p_b_p_b
- 组题人：Qingyu
- 题解：alpha1022, feecle6418, Wu_Ren, p_b_p_b
咖啡 (Div. 2 Only)
来源：
- Nordic Collegiate Programming Contest 2022. Problem C. Coffee Cup Combo
- https://qoj.ac/contest/1024/problem/4990
Tutorial by alpha1022.
不妨采用贪心策略：能喝则喝。
从左往右扫描，维护当前手中有几杯咖啡即可。
画图 (Div. 2 Only)
来源：
- All Ireland Programming Olympiad 2017 National Finals. Problem C. Paint bucket
- https://qoj.ac/contest/11/problem/48
Tutorial by alpha1022.
采用深度优先搜索或广度优先搜索得出 $(x,y)$ 所在的连通块并染色即可，需要保证每个格子不被重复访问。
治病 (Div. 1 + Div. 2)
来源：
- Petrozavodsk Winter 2020. Day 4. Yandex Cup 2020. Problem B. Bad Doctor
- http://qoj.ac/contest/444/problem/686
Tutorial by feecle6418.
首先我们要算出，如果不忽略任何医生，尼特花费的钱数。根据题意我们知道，对于某种药片，尼特吃这种药片的时间就是所有医生药方里的时间的并集，也就是给出一些区间让你求并。这是经典问题，按照左端点从小到大排序，维护当前最大的右端点即可。
如果忽略某个医生，只需要找到只被这一个医生覆盖的 (药片,时间) 二元组，把这些二元组的贡献减掉。对每种药片分开考虑，也就是对每个区间，求出只被这一个区间覆盖的位置的总长度。首先用差分求出每个位置被覆盖了多少次，找出只被覆盖一次的位置，把这些位置的权值赋值成 1，对权值做前缀和，然后求出每个区间内的位置的权值之和，就是只被这一个区间覆盖的位置的总长度。
所有差分、前缀和都需要在离散化之后的坐标上进行，瓶颈在于离散化，总时间复杂度为 $O((\sum K)\log (\sum K)+n+m)$。
拓扑序计数 (Div. 1 + Div. 2)
来源：
- Petrozavodsk Winter 2020. Day 4. Yandex Cup 2020. Problem C. Topological Ordering
- http://qoj.ac/contest/444/problem/687
Tutorial by feecle6418.
设 $f(S)$ 表示按照拓扑序从前往后的顺序加点，初始为空集，到已经加入 $S$ 这个点集，这一段的加点方案数。设 $g(S)$ 表示按照拓扑序从后往前的顺序删点，初始为全集，到现在还剩下 $S$ 这个点集，此时删除顺序的方案数。$f,g$ 都可以在 $O(2^nn)$ 时间内简单地 dp 求出。
对于给定的 $u,v$，$u$ 在 $v$ 前，就是要，拓扑序加入 $v$ 那一刻，$u$ 已经在拓扑序里了。所以，$ans_{u,v}=\sum [u\in S,v\notin S]f(S)g(S\cup \{v\})$（枚举加入 $v$ 之前一刻，有哪些点加入了拓扑序）
直接实现该算法的时间复杂度为 $O(2^nn^2)$，但 $S$ 的枚举有 $1/4$ 的常数，已经可以过。
当然，上述算法还可以继续优化到 $O(2^nn)$：枚举 $S,v$，相当于 $\forall u\in S$，$ans_{u,v}$ 都加上一个定值。因此瓶颈在于：“给出 $a_{0}\sim a_{2^n-1}$，对所有 $u$ 求出 $\sum_{u\in S}a_S$”。可以用下面的方法：
for i from n-1 downto 0:
for j from 2^i to (2^{i+1}-1):
ans[i]+=a[j]
a[j-2^i]+=a[j]最后 $ans_u$ 就是答案。因此我们把 $O(2^nn)$ 的循环优化到了 $O(2^n)$。（但是实际上速度仅仅变快了不到一倍）
序列 (Div. 1 Only)
来源：
- Petrozavodsk Winter 2021. Day 4. PKU Contest (Common Contest 1). Problem H. Longest Loose Segment
- http://qoj.ac/contest/532/problem/894
Tutorial by Wu_Ren.
由于答案有可二分性，直接获得 $O(nm\log n)$ 做法。
下面是正解：
考虑每次建出小根笛卡尔树，并且在笛卡尔树上 dp。
我们对于每个节点，维护子树内 $a_i$ 最大值 $mx$，区间长度 $sz$，最长合法子段长度 $len$。
假设 $u$ 的两个儿子为 $lc,rc$，那么考虑合并 $lc,rc$ 的信息来得到 $u$ 的信息。
$mx,sz$ 的合并是显然的。考虑 $len$ 的合并，首先，假如合法子段不经过 $u$，那么就是 $len_u\leftarrow \max(len_{lc},len_{rc})$。假设存在 $u\in[l,r]$ 使得 $[l,r]$ 是合法子段，那么假设 $\max\limits_{i\in[l,u-1]} \{a_i\}\ge \max\limits_{i\in[u+1,r]} \{a_i\}$，此时我们可以发现，如果 $l>u-sz_{lc}\land r>u$，那么 $[l-1,r-1]$ 也是合法的。
那么就可以知道，我们可以认为跨越 $u$ 的合法子段要么一个端点是 $u$，要么一个端点是 $u-sz_{lc}$ 或 $u+sz_{rc}$。
这里可以发现，假如 $[l,u]$ 是合法子段且 $l>u-sz_{lc}$，那么 $[l-1,u-1]$ 也是合法子段，所以说一个端点是 $u$ 且另一个端点不是 $u-sz_{lc}$ 或 $u+sz_{rc}$ 的情况一定不优于 $\max(len_{lc},len_{rc})$。
那么我们只需要考虑一个端点在 $u-sz_{lc}$ 或 $u+sz_{rc}$，并且过 $u$ 的情况了（也就是说，我们只需要考虑至少把一颗子树完全包含的情况），这个转移是显然的。
复杂度 $O(nm)$。
水果 (Div. 1 Only)
来源：
- (Singapore) National Olympiad in Informatics 2022. Problem E. Fruits
- http://qoj.ac/contest/919/problem/3875
Tutorial by p_b_p_b.
为了方便，先把 $a_i\ne -1$ 且无论如何都无法成为前缀最大值的水果删掉。
为了方便，再把水果的美味度修改一下，使得没有确定位置的水果的美味度是 $1,2,\cdots,m$ ，而确定位置的水果的美味度则是夹在中间的小数。
设 $a_1,\cdots,a_n$ 是读入的方案，$A_1,\cdots,A_n$ 是最终的方案。
放弃思考，直接设 $dp_{x,v}$ 表示确定了 $A_1,\cdots,A_x$ ，且其中最大值小于 $v+0.99$ （$v$ 是整数），考虑如何转移。
- 如果 $a_x\ne -1$ ，那么有两种选择
- 让 $a_x$ 成为最终的前缀最大值，那么从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移。
- 扔掉 $a_x$ ，从 $dp_{x-1,v}$ 转移。
- 如果 $a_x=-1$ ，再分两种
- $a_1,\cdots,a_{x-1}$ 的最大值小于 $v$ ，那么这里肯定应该贪心放 $v$ ，从 $dp_{x-1,v-1}+c_v$ 转移。
- 否则这里只能被迫开摆，随便放个以后不用的小的，从 $dp_{x-1,v}$ 转移。（注意因为我们做过预处理，所以这里总是可以保证不超过 $v$ 。）
于是就获得了一个非常垃圾 $O(n^2)$ 做法，下面考虑优化。
- 对于 $a_x\ne -1$ ，注意到 $dp_{x,0},\cdots,dp_{x,m}$ 单调不降，因此一定是一个前缀从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移，而其他地方直接把 $dp_{x-1,v}$ 拉过来。因此只要二分分界点就可以直接前缀赋值。
- 对于 $a_x=-1$ ，显然只有一个合法状态会从 $dp_{x-1,v}$ 转移，剩下的都从 $dp_{x-1,v-1}+c_v$ 转移。不过这个怎么维护呢？
设 $S_i=\sum_{j=1}^i c_j$ 表示 $c$ 的前缀和。另外设 $pre_x$ 表示 $a_1,\cdots,a_x$ 有几个 $-1$ 。
对每个 $dp_{x,v}$ 维护一个二元组 $f_{x,v}=(x',y)$ ，表示 $dp_{x,v}=S_v-S_{v-(pre_x-x')}+y$ ，那么就做完了：从 $dp_{x-1,v-1}+c_v$ 转移，就等价于 $f_{x,v}=f_{x-1,v-1}$ 。而其他转移也都是简单的单点或区间赋值。
暴力线段树就能维护了。还可以再好看一点，用双端队列来维护二元组的连续段，但其实区别不大。
