显然 f [ i ] [ j ] f[i][j] f[i][j] 表示前 i + j i+j i+j 个，有 i i i 个用 a a a ， j j j 个选 b b b 的方案数。然后显然。
不是，好像假了， k + s ≠ n k+s\neq n k+s=n
直接按 a a a 排序，那样子只要不选 b b b 的肯定选 a a a。
除了dp，也可以费用流。
源点连两个虚点，分别跑 X , Y X,Y X,Y 流量。然后连到每个点流量1费用 a i , b i a_i,b_i ai,bi 即可。
首先肯定两维排序。
假设全部选 a a a，然后把一些换成 b b b。那直接作差排序即可。
按 a i − b i a_i-b_i ai−bi 排序。
必然存在一个地方，前面全部选编程，后面全部选体育。
但是中间会有一些空洞。
考虑枚举前缀（分割线），前缀里选编程的肯定是选 a i a_i ai 最大的，后缀中选 b i b_i bi 最大的。
前 i i i 个的topk的sum是好求的。
然后就完成了。
三项技能。后面会讲。
如果还有分割次数显然选最大块的分割。
但是对于一个块，如果最后分了两次，显然不是对半分。
我觉得直接二分最大块长度应该就行了。
假设只切一个，就选最大的。
但直接增量来做是不对的。
最终局面：选出若干个胡萝卜，这些胡萝卜是一步到位切成的。
问题是每个胡萝卜要切多少份？
想象中先把切开的合起来，再重新切，也就是有一个反悔的过程。
也就是把增量的过程变成切 k k k 刀变成切 k + 1 k+1 k+1 刀的情况。
我觉得我的做法没问题。
从D回来，显然满足是上凸的，因为收益越来越小，二分斜率。
当然，也可以二分最后一次的收益。
相当于每个数可以加 k k k，然后求差分序列大于0的数之和（初始时0）
如果设计 f [ i ] [ j ] f[i][j] f[i][j] 表示 a i = a i + k × j a_i=a_i+k\times j ai=ai+k×j，这样子显然是没问题的。
这是 n 2 n^2 n2，第二维能不a，能搞一下呢？
首先转化和我的一样。
对于上面那个 f f f，显然 j j j 只会转移到 j + 1 , j , j − 1 j+1,j,j-1 j+1,j,j−1 ，而且如果比他小只会+1，比他大只会-1。
考虑最终答案肯定是 min f [ n ] [ 0 … n ] \min f[n][0\dots n] minf[n][0…n]。但最小值一定是 f [ n ] [ 0 ] f[n][0] f[n][0]，因为最后一个显然取最小是没问题的。
所以前 i i i 个的最优在 f [ i ] [ 0 ] f[i][0] f[i][0] 处取得，有 d p i = f i , 0 dp_i=f_{i,0} dpi=fi,0，但这样没法做转移。
比如
a
i
<
a
i
−
1
a_i
好，现在考虑会 a i > a i − 1 a_i>a_{i-1} ai>ai−1，现在本身要花费 d i d_i di 的代价，但如果你用之前的 k − d i k-d_i k−di，那么就不需要执行这个操作了。
其实就是要么按原计划，要么在之前下沉一轮。
那现在需不需要把 d i d_i di 放进去呢？
嗯，是需要的，因为未来可能是有更差的。
考虑二分图匹配。每个 a i a_i ai 只能向编号大等于它的 b i b_i bi 连边。
可以直接变成一条链，源点向每个点连，再向汇点连。那样子即可。
好像不是网络流，是费用流？
建图方法和我一样。跑最小费用流。
复杂度没问题。
模拟网络流。对所有 a , b a,b a,b 一起排序。
a a a 相当于后缀加。 b b b 在有的情况下是后缀减，没的情况直接丢到一个小根堆里。
好像堆不行？开两棵线段树似乎就行了？
假设画一个流的次数和总费用的图像，这显然是下凸的。（也就是增量越来越大）
现在要求这个图像横坐标为 k k k 的费用。
此时我们可以使用wqs二分。
假设斜率match，则截距最小。这应该是wqs二分的内容吧，我记得不太清了
因此对于给定斜率可以求出给定截距最小，这个截距怎么得呢？
有 d = f i − i k d=f_i-ik d=fi−ik。求 min f i \min f_i minfi，反求 min f i − i k \min f_i-ik minfi−ik，此时在看一下这个 i i i 是什么东西。
因此我们先二分（枚举斜率），现在可以选任意多个 a i , b i a_i,b_i ai,bi，只需要满足他们的集合大小相等，且每次选中一个 a i a_i ai 会扣除 k k k 的费用，求最小费用。（因为横坐标每-1，相当于每减一个，就会小 k k k）
可以先把所有 a i − k a_i-k ai−k。然后现在要求 min ( ∑ b i − a j + k ) \min (\sum b_i-a_j+k) min(∑bi−aj+k)，这个变成了低买高卖股票这个经典的普及组问题。
遇到 a i a_i ai 塞入队列，遇到 b i b_i bi 先优先和 a i a_i ai 配对，然后把 − b i -b_i −bi 扔回进去，因为 b i b_i bi 也是可以反悔的。同时在此记录选了多少个，然后调整斜率。
wqs发现是凸的一般有：
同bonus1。
刚刚做法是wqs二分的局限。
某个东西wqs可做，现在每个都要做，则使用闵可斯基和的算法。
正常容易分治。左右返回的结果都是凸的，然后就可以合并。
但这题不容易分治。因为返回的是 n 2 n^2 n2 的东西，表示选了多少个 a a a，那边选了多少个 b b b。
但ABC上上周的最后一题用的是闵可夫斯基和。
对于这题还可以用线段树来做。
把它想象成选 a i a_i ai 是左括号，选 b i b_i bi 是右。然后用线段树维护只选左，只选右，选左+右的代价。
但是第二次可能可以选右+左 ()()，但有些时候也不行。
用左+右是可行的，用右+左不一定行。
本质是括号匹配中对于这些括号是不会退流，但是配对会退流。
对于目前选右+左，只需要满足前缀和>0，就可以。
但这样子不能用线段树简单维护，因为可能出现这样子的情况，[()()()]，会新增很多不连读段。
因此要多维护几个东西。
区间最大r在l前的东西。
区间内前缀和最小的值 v 1 v_1 v1
区间内RL从大于最小值的地方返回的RL‘。
我们在某些时候可以把第一种转化为第三种。
然后每次选左右括号，然后区间±1，然后还有各种更新。
其实是利用12中的辅助信息求出3的信息。
打完后还是感觉wqs比费用流好打（如果copy板子很难说）
但考场上打wqs直接飞起
同样，直接对敌人强弱排序，然后连边，但此题变成费用流了。
对 a a a 的加入显然是有序，另一边按 − b + c -b+c −b+c 排序后加入，应该就和上一题一样了。
题目钦定红点在蓝点前面，匹配有价值，和上一题一模一样。但这题不限选次数，所以其实就是wqs二分内部的判断。
50分显然。
正解我想想。
把负的去掉，变成一段段。
奇数位放上面，偶数位放下面，然后奇数和前后偶数相连。然后前后都连1的流量，中间边是两个点的max值。那样子肯定就符合。
因为此时是凸的可以wqs二分。
这题可以更简单。
假如 k = 1 k=1 k=1，只会选最大的。
从变大的过程中，如果出现反悔，那么肯定是相邻的两条都同时选中。
考虑现在变成另一个问题，一开始选择一个最大价值。一个不选，相当于左右都选。我们在左右连一条边。由 b + c b+c b+c 取代 a a a。代价是 x = b + c − a x=b+c-a x=b+c−a，并把原先3个破坏掉。
然后可能又会连一条 x + e − d x+e-d x+e−d。
因此每次选了一个，直接把相邻3个全部删掉，然后在加入新的收益。
听说是道很厉害的贪心
首先是不是凸的？显然不是 。
按某个规则排序？
按照 b i b_i bi 和 2 a i 2a_i 2ai 的关系。
b i > 2 a i b_i>2a_i bi>2ai 可以拆成两个东西考虑。
b i < 2 a i b_i<2a_i bi<2ai，如果选 a a a 那么只会选一个。也就是按 b i b_i bi 排序，在后缀里面选最小 a i a_i ai。
对于两类，分别选 t t t 个的答案都是易求的。
如果对于每个 k k k 都要输出呢？能不能闵可夫斯基和？
考虑函数虽然不凸，但如果分成两类，而且是直接奇偶分，那样子两个子函数都是凸的。
此时我们就可以分治。传入 [ l , r ] [l,r] [l,r]，吐出一个一维的 [ i , f i ] [i,f_i] [i,fi]，会分成 [ l , m i d ] , [ m i d + 1 , r ] [l,mid],[mid+1,r] [l,mid],[mid+1,r]。分别把奇偶节点取出来，都是凸的，分别做闵可夫斯基和，两个独立的都是凸的。（要分讨是奇偶偶奇和奇奇偶偶）
对于第一种做法，在 b < 2 a i b<2a_i b<2ai 时，还需分讨一下。
不知道为什么是交互。
从左到右做，并且每一次钦定当前元素只和前面的连接的当前最小费用。
虽然这不是最优的，但我们有当前最优结果，我们现在要允许他可以反悔。虚拟无穷红蓝点。
假设B-R连（只出现过一个B），How允许反悔呢？
假设未来有个B‘，未来的最优决策是和R连，那么这个R就可以不和原先的B连。新代价是 B − R B-R B−R，反悔代价是 R − b R-b R−b、
令 f = − R − ( R − b ) f=-R-(R-b) f=−R−(R−b) 塞到红色的反悔堆里面去。遇到蓝色节点就从红色点堆里取，此时是 B + f B+f B+f。
所以我们并不是和上一个最近的相连，而是取出不同颜色反悔堆中取出。我们要 w = min ( R − b , R + f ) w=\min(R-b,R+f) w=min(R−b,R+f)，同时塞入 − w − R -w-R −w−R。其中 b b b 表示最近颜色。（ R − b R-b R−b 就没必要塞到反悔堆里面了为什么我感觉需要啊？）
事情还没结束。R BBBBBBBBBB，后面这些B都会连前面的R。现在有了一个R，那肯定会有一堆B和这个R连。
因此我们要在堆里面取出尽可能多的 R + w R+w R+w， w w w 落在蓝色队列里面的东西。不需要丢回红色堆里。因为对于这个红色点来说只会反悔一次。
这里有几个地方值得思考：
我们每次反悔肯定会满足之前都能匹配。
我们就是要先满足当前自己的匹配。
然后去把之前对于旧有匹配不满意的对方颜色进行翻转。
丢个聊天记录：
我：
老师，那道G题红蓝反悔匹配那题，是不是对于每个颜色操作时只需要往堆里丢一次啊？
每个颜色要先满足自己的匹配，而只需要在这个时候丢进去
然后解决掉前面其他可能对现状不满意的匹配，这步需不需要仍到对方颜色的堆里啊？
我刚刚感觉似乎不太需要，但现在感觉可能又需要。如果丢进去的话此时f就不是我们一开始推出的-2R-B了，而是只含-R
我的意思大致就是说现在到红色点，肯定只需要往红色点里面丢一次。但是帮助其他蓝色点的匹配是否需要往蓝色堆里面扔？
还有另一个问题就是你上课当时说如果这个R和B匹配是和最近B匹配而不是反悔某个B，那样子就不需要丢到红色堆里。这里不太理解，我感觉是需要丢进去的吧？
老师：
需要，因为那个不满的蓝色可能将来和其他红色匹配更佳。
也是需要的。
我刚刚也交了一发代码到比赛里
A题的bonus2
显然我还没想到。
假设先全选 a i a_i ai，剩下的代价就是 b i − a i , c i − a i b_i-a_i,c_i-a_i bi−ai,ci−ai。
然后就和A的bonus1一样了。
从费用流角度来思考。
左边有 n n n 个点，右边有10个点。每个人连向右边一个点。然后中间连边 ( 1 , c i , j ) (1,c_{i,j}) (1,ci,j)，然后向终点连 ( a j , 0 ) (a_j,0) (aj,0)。
每一次每个人就是选最小边，然后流过去。
我们考虑逐个加人，每个人尝试选最小边。但如果爆了，就要返流了。
对于第 i i i 个人，可能发生 i − 1 i-1 i−1 次返流。
返流相当于走最短路，而最短路每个点最多走两次，那样子返流长度不会超过20。
但复杂度还是不对，因为你不知道返流走那条路是最优的，因为会扩展到 n n n 个节点。
考虑往回增广到左边节点，我们并不关心新拓展到的节点，我们只关心从右边的节点走到右边的节点。
如果我们每次处理好了右边的Floyd矩阵，但要保证不共享左边的点。
怎么保证？考虑第一次，求出最短路为 ( 1 , i ) (1,i) (1,i)，费用是 c 1 , i c_{1,i} c1,i。未来某个时刻希望1流向 j j j，相当于发生了 d [ i ] [ j ] = c 1 , i − c 1 , i d[i][j]=c_{1,i}-c_{1,i} d[i][j]=c1,i−c1,i，但并不知道去 ( 1 , j ) (1,j) (1,j) 还是 ( 1 , k ) (1,k) (1,k)。对于每个 j j j，又要往Floyd矩阵上转。但现在不是矩阵了，是一个set了。把 c 1 , i − c 1 , i c_{1,i}-c_{1,i} c1,i−c1,i 塞入 s e t [ i ] [ j ] set[i][j] set[i][j]，那样子可以快速求出当前最短路。然后再重新塞回set里。
但这样子只能保证这一次正确，不能保证未来正确。
因此我们要重新调整set。
真无语了，这题调了半天就是set只按了其中一维排序，这时就算另一维不同set也会合并在一起。果然一段时间没打代码码力严重下降。