这里应该有一些理论，但是先咕咕咕了。
ICPC2014 WF Buffed Buffet
我们对两种食物分开考虑。先考虑连续的食物，发现实际上需要对若干个个二次函数做闵可夫斯基和。因为二次函数求导以后是一次函数，复合后只有 \(O(n)\) 个拐点，可以直接暴力维护出取 \(1\dots m\) 的最大值，这里复杂度是 \(O(n+W)\) 的。
然后是离散的食物，二次函数是满足四边形不等式的，所以按照 \(\bmod w\) 分类之后就可以直接决策单调性了。时间复杂度 \(O(nW\log W)\)。
最后合并一下就行。
UER #8 雪灾与外卖
考虑 DP，设 \(dp_{i,j}\) 表示你到了第 \(i\) 个位置，现在有 \(j\) 个餐馆的菜在往后跑。\(j\) 可以是负的，表示有 \(|j|\) 个外卖员在往前跑。
我们考虑这个 DP 要干什么：
- 对于每个 \(j\)，让 \(dp_{i,j}\) 加上 \(w|j|\)。
- 左移一位。
- 和 \(c\) 个 \(w\) 进行 \((\min,+)\) 卷积。
可以归纳证明其是凸的，所以可以直接上 slope trick。注意要将斜率相同的合并，否则复杂度是错误的。
CFgym102331J Jiry Matchings
首先序列上是经典反悔贪心，另外可以利用其凸性用分治+闵可夫斯基和解决。
上树之后我们发现反悔贪心好像不是很好反悔，一条链反悔之后新增的端点是不确定的而不是向链上一样容易确定，所以我们大概（？）只有闵可夫斯基和一条路可以走了。
但是如何分治？如果用点分，那么特别是到点分树下层需要记录点的选择信息过多，复杂度得不到保证。如果是用链剖，我们发现这个就非常好，因为我们已经有成熟的链上算法了。
具体的，我们将这棵树重链剖分，然后对于每个点用哈夫曼树合并其轻子树的信息，用分治合并重链上的信息，容易证明两者的复杂度都是 \(O(n\log ^2n)\) 的，空间 \(O(n\log n)\)，可以通过。
另外我每个点暴力合并过了，和哈夫曼树跑的差不多快。
国家集训队胡策 Tree I
WQS 二分之后求答案就好了，复杂度 \(O(m\log m\log V)\)，用归并可以做到 \(O(m\log m+m\log V)\)。
CFgym102331H Honorable Mention
首先先建立一颗线段树，用闵可夫斯基和合并出线段树上每个节点左右端是否有往外延伸的最优答案。
然后对于每个询问 WQS 二分，然后在线段树上每个凸包上二分出最优转移点，然后计算答案，这样是 \(O(n\log ^3n)\) 的。
考虑整体二分，这样线段树上每个节点就只用 two-pointers 了，复杂度降至 \(O(n\log ^2n)\)。
[WC2020] 选课
WC 不选国家队就变成这样了吗/jy
首先我们先来考虑 \(p=0\) 的情况。记 \(L=T-\sum\limits_{i=1}^{m}{s_i}\)，则我们只需要对于每个分类求出学分在 \([s_i,s_i+T]\) 范围内的最小脑力值，然后将其合并到整体的一个 DP 上即可。合并的过程是 \(O(mL^2)\) 的，当然可以凸优化成 1log。
对于每个分类，一个无脑的做法是将课程按照学分分类，然后排序后显然满足四边形不等式，直接决策单调性合并即可。复杂度 \(O(N\log N)\)。当然你可以不那么暴力，枚举 \(3\) 选了几个，然后 \(12\) 贪心即可，复杂度是 \(O(N\log N+NL)\) 的。
然后如果按照原题面其实是不太会怎么做的，但是实际数据满足所有 \(p\) 关联的课程不超过 \(12\)，因此直接 \(2^{P}\) 枚举关联到的课程是否选择，然后剩下的按照上面提前预处理出来就好了，这一部分时间复杂度 \(O(2^PPL^2)\)。
总复杂度 \(O(mL^2+N\log N+2^PPL^2)\)，反正是个缝合怪。
CFgym102586B Evacuation
首先我们设中点为 \(mid\)，然后分 \([l,mid]\) 和 \([mid+1,r]\) 两类讨论，这样每一类就只受一边的限制了。
然后你发现在确定限制和起始点的情况下，贡献是可以 \(O(1)\) 计算的，并且满足四边形不等式，那么就可以决策单调性优化了，吗？
好像不行，因为每个询问有一个询问范围，所以不能直接决策单调性。
考虑建立一棵线段树，每个询问放到线段树上的对应区间里面去，然后这样线段树上每个节点对应的询问就没有范围问题了，就可以直接决策单调性了。
ZJOI2020 序列
怎么这个对偶这么厉害？
首先我们将其转化为一个线性规划问题。对于每种操作记一个操作次数 \(x_i\)，则对于每个位置，有 \(\sum x_j \geq a_i,-\sum x_j \geq -a_i\)。
考虑其对偶问题，这相当于要给每个位置赋一个可正可负的权值 \(b_i\)，并且对于每个操作，其涉及到的元素的权值和 \(\leq 1\)。
我们首先证明，每个位置的 \(b_i\) 范围是 \([-1,1]\) 范围内的。
\(b_i\leq 1\) 是显然的，我们考虑反证 \(b_i<-1\)。
如果没有包含 \(b_i\) 的区间 \(=1\)，则将 \(b_i\) \(+1\) 会让答案更优。否则，考虑这个区间除掉 \(b\) 的左半边和右半边，总有一边 \(\geq 2\)，与假设不符。所以 \(b_i\) 一定可以调整在 \([-1,1]\) 区间内。这样我们就可以写出一个四方的 DP 了！
考虑那个四方的 DP，我们需要记录三种操作的前缀最大值是什么，我们仍然可以仿照上面的方法证明前缀最大值 \(\geq -1\)，所以我们的 DP 状态后三维是 \(O(1)\) 的，因此总共就是 \(O(n)\) 的了！
How to Create a Good Game
以下内容搬运自 dxm 的论文
考虑对每个点分配标号 \(p\)，使得对于每条边，有 \(p_x-p_y\leq -w\)，以及 \(p_{n-1}-p_0\leq D\)，并且要求 \(\sum p_y-p_x-w\) 最大。
对其对偶，得到我们需要对每条边分配标号 \(e\)，使得对于每个点，其出边的 \(\sum e_i\) 减去其入边的 \(\sum e_i \geq\) 这个点的入度减出度，要求最小化 \(\sum e_iw_i\)。
考虑用网络流模型来刻画这个事情，将每条边的 \(e_i\) 看成其流量， \(w_i\) 看作其费用，然后对于每个点，设 \(in_i\) 为其入度减出度。若其 \(in_i\geq 0\)，则从源点向其连流量为 \(in_i\) 的边，反之让其向汇点连流量为 \(-in_i\) 的边。
等下，你先别急，对于其向汇点连的边，其意义是正确的，是限流。但是对于源点向其连的边，限流的意义是不正确的。真正的做法应该是至少要流 \(in_i\)。但是上面的做法却是对的，原因是因为我们跑的最小费用在最大流的前提下。汇点的意义正确，并且其会流满，所以，源点也需要流入这么多流量。又因为 \(\sum in_i=0\)，因此流入源点的流量均会顶到上界，所以是正确的。
这也给了我们求一类形如 \(\sum x_iw_i+\sum w_{u,v}\max(p_u-p_v-c_{u,v},0)\) 的方法：先对偶，然后就可以转费用流，利用其度数和为 \(0\) 的性质求出正确的最小费用。
AGC045F Division into Multiples
首先我们考虑给这个东西先搞成互质。如果 \(\gcd(A,B,C)>1\) 就可以直接除掉。 然后如果 \(\gcd(A,B)>1\) 也可以直接除。如果 \(\gcd(A,C)>1\) 那么 \(B\) 一定是要这个 \(\gcd(A,C)\) 倍数的，那么给 \(Y\) 除上 \(\gcd(A,C)\)，然后 \(A,C\) 除掉。\(B,C\) 也是一样的，所以可以搞成两两互质。
搞成两两互质之后，题目的要求就是 $Ax+By\equiv 0\pmod C $，移项一下就是 \(y=-\frac{A}{B}x\bmod C\)。也就是说我们设 \(k=-\frac{A}{B}\bmod C\) 之后，那么 \(y=kx \bmod C\)。
进行一些观察，我们发现只有前缀最小值是有用的。并且你打个表出来发现这玩意是凸的。
考虑反证：假设存在相邻的三个点满足 $$
标签：每个,submission,复杂度,然后,优化,sum,log From： https://www.cnblogs.com/275307894a/p/17934638.html