省流：ABC过水，DE说得过去
你AT还在蒸蒸日上
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A:
ans=12a+bans=12a+bans=12a+b，秒了。
B:
纯模拟，过。
C:
贪心，按照 pi+wip_i+w_ipi +wi 的顺序排序得出排序 a′a'a′，可以证明这一定是最优的
于是我们枚举 kkk 从 n→0n \to 0n→0，显然，若存在 ∑1≤i≤kwi≤∑k+1≤i≤npi\sum_{1 \le i \le k}w_i \le \sum_{k+1 \le i \le n}p_i∑1≤i≤k wi ≤∑k+1≤i≤n pi ，立刻输出 kkk 即可。
代码略，下边给出策略证明：
设 SSS 为乘坐雪橇的驯鹿集合。则题目条件可表示为：
∑i∉Spi≥∑i∈Swi\sum_{i \notin S} p_i \geq \sum_{i \in S} w_i i∈/S∑ pi ≥i∈S∑ wi
将 ∑i∉Spi=∑i=1npi−∑i∈Spi\sum_{i \notin S} p_i = \sum_{i=1}^n p_i - \sum_{i \in S} p_i∑i∈/S pi =∑i=1n pi −∑i∈S pi 代入上式，可得：
∑i∈S(wi+pi)≤∑i=1nPi\sum_{i \in S} (w_i+p_i) \leq \sum_{i=1}^n P_i i∈S∑ (wi +pi )≤i=1∑n Pi
由于等式右侧为常数，最优策略就是按照 wi+piw_i+p_iwi +pi 排序。
D:
推理，对于 aia_iai ,令其在 bbb 中第一个 >=ai>=a_i>=ai 的下标为 rtrtrt,smi=∑1≤j≤ibism_i=\sum_{1 \le j \le i}b_ismi =∑1≤j≤i bi ,易证易得 aia_iai 的贡献为：
∣smrt−1−(rt−1)ai)∣+∣(smm−smrt−1)−(m−rt+1)ai∣|sm_{rt-1}-(rt-1)a_i)|+|(sm_m-sm_{rt-1})-(m-rt+1)a_i| ∣smrt−1 −(rt−1)ai )∣+∣(smm −smrt−1 )−(m−rt+1)ai ∣
读者自证不难
用二分和前缀和分别计算 smism_ismi 和 rtrtrt 即可
代码：
E:
谁懂我最后一分钟调出来的救赎感
注意到对于数列 AiA_iAi ,他总是可以从 A0A_0A0 经过一系列操作到达，于是我们考虑建立数列间的关系树。
(以下定义 SSS 为下标不同但字典序相同的数列，可以理解为一个数列的重复，但下方推理时默认其为一个数列)
于是我们可以定义 idxAiidx_{A_i}idxAi 为数列 AiA_iAi 在关系树中对应的节点， add(A,v)add(A,v)add(A,v) 意为在数列 AAA 后加入一个数 vvv 后所得到的新数列，然后定义 trS,vtr_{S,v}trS,v 为数列为 add(S,v)add(S,v)add(S,v) 的集合。
如果还不能理解，请结合下图理解：
最后，题目要求输出 A1,A2,⋯ ,AnA_1,A_2,\cdots,A_nA1 ,A2 ,⋯,An 的字典序排序，只需要按照我们这里建立的关系树，从 0(A0(∵idxA0=0))0(A_0(\because idx_{A_0}=0))0(A0 (∵idxA0 =0)) 开始，按照 trS,vtr_{S,v}trS,v 中 vvv 的大小升序遍历，每到一个非根节点就输出当前节点中 SSS 所存储的所有数列小标即可，可以证明这是对的。
当然，如果还不懂的话，建议看看下方代码，有详细的解释（比赛结束后加的）。
代码：
