贪心与DP记录/计算几何能做的

## $[HNOI2018]$排列&[集训队作业2018]三角形 这题我写了个自认为正确的贪心，交上去获得了40分暴力分的好成绩。 结果回头一看我连第三个样例都没过~~，改了之后交上去就只有30分了~~。 首先我们看看第一个题。 题目很绕，我们忽略它的数学表达，直接从中抽象出实际关系，也就是如果你选了第$i$个数，那么第$a_i$个数就不能选到它的后面了。 那么我们从$a_i\to i$连边，表示先选$a_i$才能选$i$。于是只要出现环就无解，那么最后我们会形成一棵森林。 考虑如何贪心。正着贪反着贪都是错的，你可以发现我们可以通过给更大/更小的点让位置的方式来使答案更大。 假设我们已经知道了全局最小点，那么在它的父亲被选之后，这个点一定最先选择，那我们可以将这两个结点合并。 那么在合并后会出现一堆序列，我们怎么找最优点（序列）呢？ 考虑两个序列$a,b$的权值和是$W_a,W_b$，个数是$n_a,n_b$，再假设我已经选了$i$个数了，那么它们顺着合和反着合的贡献分别是 $$V_{ab}=\sum_{j=1}^{n_a}(i+j)w_{a_j}+\sum_{j=1}^{n_b}(i+j+n_a)w_{b_j}$$ $$V_{ba}=\sum_{j=1}^{n_b}(i+j)w_{b_j}+\sum_{j=1}^{n_a}(i+j+n_b)w_{a_j}$$ 那么$V_{ab}-V_{ba}=n_aW_b-n_bW_a$。 若这玩意儿$>0$，那么$\frac{W_a}{n_a}<\frac{W_b}{n_b}$，也就是平均权值小的更优秀。 我们按这个贪心每次合并就可以了，合并时产生的贡献就是$W_x\times n_{fa_x}$，因为你要先把父亲的序列选了，那么这个点的费用就会多$n_{fa_x}$倍。 实现可以用可删除堆，然后最好弄个零结点方便算最后的贡献。 三角形咕咕咕了。 ## $[AGC015E]Mr.Aoki\ Incubator$ ## $[JSOI2018]$部落战争 $70pts$大概是运用解析几何的知识求下每个横纵坐标的$A$凸包边界，或者直接$O(\log n)$判一下是否在凸包内，复杂度是$O(qn\log n)$的。 $100pts$其实我并不知道为什么可以直接这样转换。