排序贪心是贪心的经典形式。具体来说，如果能证明某些逆序对总能被调整成更优的形式（例如邻项交换或者把最值换到开头结尾），我们就可以立刻得到最优解中不存在这种逆序对，于是最优解可以排序后考虑。
更一般的最优性调整法，其实也可以被看成一种“逆序对”调整：一个调整规则 Δ\DeltaΔ 通常可以表述为：一个解（或者最优解）中（满足某种条件）的局部 xxx 调整成局部 yyy 一定会变得更优。这可以视为一种局部之间的偏序 x⪯yx\preceq yx⪯y，且最优解只需要在 ⪯\preceq⪯ 的极值上考虑。然而，一般的偏序的极值性质并不好，有没有什么偏序的极值是好的呢？
二维偏序满足这一点，二维偏序的极值是垂直方向上的一个单调序列/折线。（或者说，极值一定是反链，而二维偏序的反链是互补的二维偏序上的链，即上升子序列，或者说画到平面上是折线。）
因此，不仅排序贪心（一维的全序或者接近全序）可以做，基于二维偏序（比如区间、或者两个值）的调整也都可以做，即可以用平面上的折线刻画最优解的形式。请你完成以下问题：
问题1. 有 nnn 种商品，在 X,YX,YX,Y 两家商店出售，第 iii 种商品在两家商店的价格分别是 xi,yix_i,y_ixi ,yi 。价格都是 ≤109\leq10^9≤109 的正整数。现在每家商店各自推出了买一赠一活动，买一件商品可以任选赠送至多一件同商店的商品。
你要获取每种商品恰好各一件，并且来自两家商店的商品数量相等，最小化总花费。保证 nnn 是偶数。
n≤105n\leq10^5n≤105
问题2.1. 有 nnn 种商品，在 X,YX,YX,Y 两家商店出售，第 iii 种商品在两家商店的价格分别是 xi,yix_i,y_ixi ,yi 。价格都是 ≤109\leq10^9≤109 的正整数。现在你要在两家商店分别购买 cx,cyc_x,c_ycx ,cy 个物品且购买的物品不能重复，最小化总花费。
n≤105n\leq10^5n≤105
问题2.2. [AGC018C] 有 nnn 种商品在 X,Y,ZX,Y,ZX,Y,Z 三家商店出售，第 iii 种商品在三家商店的价格分别是 xi,yi,zix_i,y_i,z_ixi ,yi ,zi 。现在你要分别在三家商店购买 cx,cy,czc_x,c_y,c_zcx ,cy ,cz 种商品且 cx+cy+cz=nc_x+c_y+c_z=ncx +cy +cz =n。购买的物品不能重复，最大化总花费。
n≤105n\leq10^5n≤105
问题2.3. [AGC018C加强版] 考虑有四家店（或者说四种颜色）的情况，你有哪些做法？
n≤105n\leq10^5n≤105
问题3.1. [qoj9222弱化版] 有 nnn 种商品，在 X,YX,YX,Y 两家商店出售，第 iii 种商品在两家商店的价格分别是 xi,yix_i,y_ixi ,yi 。价格都是 ≤109\leq10^9≤109 的正整数。现在每家商店各自推出了买一赠一活动，买一件商品可以任选赠送至多一件同商店价格相等或更低的商品。
你要获取每种商品各一件，最小化总花费。
n≤5000n\leq5000n≤5000（原题 n≤105n\leq10^5n≤105）
问题3.2. 有 nnn 种商品和常数 kkk，在 X,YX,YX,Y 两家商店出售，第 iii 种商品在两家商店的价格分别是 xi,yix_i,y_ixi ,yi 。价格都是 ≤109\leq10^9≤109 的正整数。现在每家商店各自推出了赠品活动，每买一件商品之后可以任选赠送至多 kkk 件同商店价格相等或更低的商品。
你要获取每种商品各一件，最小化总花费。
n≤1000,k≤10n\leq1000,k\leq10n≤1000,k≤10
问题4. [P9521 JOISC2022 D1T2]
有一个 HHH 行 WWW 列的网格。第 iii 行第 jjj 列记作 (i,j)(i,j)(i,j)。网格里四个方向的相邻格子可以走。第 iii 行相邻格之间行走需要 AiA_iAi 秒。第 jjj 列相邻格之间行走需要 BjB_jBj 秒。
现在要从 (1,1)(1,1)(1,1) 走到 (H,W)(H,W)(H,W)，并且只能向行、列编号增大的方向走，请你求出最短路径。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
答案
问题1
设 k=n4k=\dfrac{n}{4}k=4n 只需要在两个商店中各买 kkk 个物品即可
能否把两个商店中买的物品分开？
对于两个物品 x1,y1,x2,y2x_1,y_1,x_2,y_2x1 ,y1 ,x2 ,y2 ，采用邻项交换的方式，比较 x1+y2x_1+y_2x1 +y2 和 x2+y1x_2+y_1x2 +y1 的大小，即比较 x1−y1x_1-y_1x1 −y1 和 x2−y2x_2-y_2x2 −y2 ，因而按照 x−yx-yx−y 排序，前一段在 XXX 店买，后一段在 YYY 店买，用堆扫一遍，预处理前缀后缀，枚举分界线，分别找 kkk 个最小价格的即可
问题2.1
没有赠送，但是告诉每个商店买多少物品，改变堆的大小即可
问题2.2
在前面按照 x−yx-yx−y 的降序排序基础上，枚举一个分界线，在前一部分中买 cxc_xcx 个 XXX 店中的物品和 www 个 ZZZ 店里的物品，在后一部分买 cyc_ycy 个 YYY 店中的物品和 cz−wc_z-wcz −w 个 ZZZ 个物品
问题转化为如何选择 XXX 店里的东西和 ZZZ 店里的东西，和上面一样，前半部分再按照 x−zx-zx−z 排序，然后用堆从前往后扫一遍维护即可
问题2.3
又多了一位，可以利用 WQS\text WQSWQS 二分降维处理
老规矩，按照 x−yx-yx−y 排序，枚举分界线，之后有一个 cz+cwc_z+c_wcz +cw 的二维情况，怎么维护？
一开始先把 ZZZ 和 WWW 两店中的物品当成能够从任何一个买，先把二者合并为一个大的限制
现在，假设在 ZZZ 商店中买了 cz′c_z'cz′ 个物品，WWW 商店中买了 cw′c_w'cw′ 个物品，判断 czc_zcz 和 cz′c_z'cz′ ，cwc_wcw 和 cw′c_w'cw′ 的大小
如果 cz=cz′c_z=c_z'cz =cz′ ，那么恰好；如果 cz′>czc_z'>c_zcz′ >cz ，买多了，那么考虑把 ZZZ 商店中所有东西涨价，让 cz′c_z'cz′ 变小；如果 cz′c_z'cz′ 因为加价加太多，需要跌价，使得 cz′c_z'cz′ 又变大，直到恰好 cz=cz′c_z=c_z'cz =cz′ 。如果 cz′<czc_z'<c_zcz′ <cz 或者考虑 cwc_wcw 也是同理
前提是与之有关的函数必须是下凸的，记选了 cz′c_z'cz′ 个 ZZZ 店里的物品，代价为 f(cz′)f(c_z')f(cz′ ) 越小越好，保证 f′(cz′)f'(c_z')f′(cz′ ) 单调递增或者 f′′(cz′)f''(c_z')f′′(cz′ ) 恒为正
因而，全选 ZZZ 或者全不选 ZZZ 店里的东西应当为代价非常大，因而需要它是一个下凸包，给下凸包加上一个 g(cz′)=kcz′(k≠0)g(c_z')=kc_z'(k\neq0)g(cz′ )=kcz′ (k=0) 的正比例函数，需要让凸包的一条边变平。改变 kkk 个大小，可以让任意一条线段变平，任意一个 cz′c_z'cz′ 都可以通过调控对应到代价的最小值。
因而，通过上面的证明，直到可以通过这样的微调而得到最终的 cz′=czc_z'=c_zcz′ =cz ，二分加的价格 ppp，得到最终的结果即可。这就是 WQS\text WQSWQS 二分
问题3.1
当 k=1k=1k=1 的时候的特例情况，同问题3.2，此处略
问题3.2
先考虑一个边界情况：假如我们已经确定好每个商品在哪个商店买，在 XXX 店里买的是 x1∼xnx_1\sim x_nx1 ∼xn ，在 YYY 店里买的是 y1∼yny_1\sim y_ny1 ∼yn ，按照降序排序，把最贵的买了，把接下来 kkk 个当赠品拿来。这样一定是最划算的
怎么确定商品在哪个商店买？不能按照前面的方式排序，因为有可能有商品是送的，无法直接计算它们的贡献
当 x1>x2,y1<y2x_1>x_2,y_1<y_2x1 >x2 ,y1 <y2 的时候，显然去 XXX 商店买 222 号商品，去 YYY 商店买 111 号商品，即便是送的也无妨
放到平面直角坐标系上，这个时候 (x2,y2)(x_2,y_2)(x2 ,y2 ) 在 (x1,y1)(x_1,y_1)(x1 ,y1 ) 的左上方，形成一个类似逆序对的情况，虽然不能够用简单的线段划开，但可以用一条单调的折线把它们分开，这条折线右下角一定去 YYY 商店买，左上角一定去 XXX 商店买
由于偏序关系一定是满足这样的情况，因而这条直线一定是单调递增的，且一定能够完美分隔
对于所有这样能够分开两部分商品的折线 LLL 取最小值，由于是整点，可以考虑对这条单调的折线进行 DP\tt DPDP，使得两部分的代价最小
为了 DP\tt DPDP 的简便，可以进行规定：
1. {xi}{yi}\{x_i\}\{y_i\}{xi }{yi } 都是整数排列，可以通过离散化进行实现，不影响 DP\tt DPDP，到时候可以还原
2. 对折线进行 DP\tt DPDP，每次往右或往上走一格，下面分给 YYY，上面分给 XXX。
3. 具体的转移式：设 dp[i][j][a][b]dp[i][j][a][b]dp[i][j][a][b] 表示向上走了 iii 步，向右走了 jjj 步，到达 (i,j)(i,j)(i,j) 位置，有 aaa 个元素归到 XXX 店，bbb 个元素归到 YYY 店。此处以折线往上走为例，一个点可能会被处理到 YYY 买，转移 dp[i+1][j][a][b+1]=dp[i][j][a][b]+ypdp[i+1][j][a][b+1]=dp[i][j][a][b]+y_pdp[i+1][j][a][b+1]=dp[i][j][a][b]+yp
4. 后续的优化：可以只存一个，因为离散化之后，a+b=i+ja+b=i+ja+b=i+j，以及其他的 DP\tt DPDP 优化
问题4
通过每行每列都有一个通行代价，行依次为 A1∼AHA_1\sim A_HA1 ∼AH ，列依次为 B1∼BWB_1\sim B_WB1 ∼BW ，从 (1,1)(1,1)(1,1) 走到 (H,W)(H,W)(H,W) 的最小代价是多少？
假设在 B1,B2,A1,A2B_1,B_2,A_1,A_2B1 ,B2 ,A1 ,A2 对应的边 X1,X2,Y1,Y2X_1,X_2,Y_1,Y_2X1 ,X2 ,Y1 ,Y2 构成的网格，先往右后往上的代价为：B1(Y2−Y1)+A2(X2−X1)B_1(Y_2-Y_1)+A_2(X_2-X_1)B1 (Y2 −Y1 )+A2 (X2 −X1 )，先往上后往右的代价为 B2(Y2−Y1)+A1(X2−X1)B_2(Y_2-Y_1)+A_1(X_2-X_1)B2 (Y2 −Y1 )+A1 (X2 −X1 )，即比较 (B2−B1)(Y2−Y1)(B_2-B_1)(Y_2-Y_1)(B2
−B1 )(Y2 −Y1 ) 和 (A2−A1)(X2−X1)(A_2-A_1)(X_2-X_1)(A2 −A1 )(X2 −X1 )，由于 AAA 对应 YYY，BBB 对应 XXX，因而移项，比较 A2−A1Y2−Y1\dfrac{A_2-A_1}{Y_2-Y_1}Y2 −Y1 A2 −A1 和 B2−B1X2−X1\dfrac{B_2-B_1}{X_2-X_1}X2 −X1 B2 −B1
代价除以间隔，有点类似在新的平面直角坐标系下的斜率定义，即比较斜率，把原来的矩形的横纵坐标分开考虑，最终走斜率较小的边
在矩形内部，考虑三条边权值为 A1,A2,A3A_1,A_2,A_3A1 ,A2 ,A3 ，对应边为 Y1,Y2,Y3Y_1,Y_2,Y_3Y1 ,Y2 ,Y3 ，同理比较 A2−A1Y2−Y1\dfrac{A_2-A_1}{Y_2-Y_1}Y2 −Y1 A2 −A1 和 A3−A2Y3−Y2\dfrac{A_3-A_2}{Y_3-Y_2}Y3 −Y2 A3 −A2 ，若满足后者大于等于前者，则类似于产生逆序对，不能插入任何不走 A2A_2A2 ，只走对应较小的那条边，最终保留 (Y,A)(Y,A)(Y,A) 形式的凸包，沿着斜率较小的边走，即可求出答案。同理可以求出
(X,B)(X,B)(X,B) 形式凸包。
总结
因而，当我们的限制是一个二位偏序的时候，也可以通过一条折线来进行描述，从而进行划分，完成贪心。
最后，买东西请不要到OI商店中购买！！！！！
