接着做昨天的题
CF1081G
这个题没自己仔细研究有点可惜。我们知道无序序列的归并排序是对每个前缀最大值分出小段然后归并若干小段，所以一次归并两边各自的相对顺序是不变的。考虑把贡献拆成区间内部的贡献和区间间的贡献。
内部的贡献是好算的：每一对元素都有 1/2 的概率贡献逆序对，于是期望就是 \(\binom n2/2\)。
区间之间的贡献也是简单的：考虑区间 A 里的第 i 个点和区间 B 里的第 j 个点，首先若 \(A[1\dots i]+B[1\dots j]\) 的最大值是 \(A_i,B_j\) 中的一个那么他一定会被排在最后没有贡献，否则就会有 1/2 的概率贡献逆序对。两个数不是 \(i+j\) 个的数的最大值的概率是 \(1-\frac2{i+j}\)。
但是这个 1/2 真的显然吗？要看你是否能找对思考路径了。考虑构造双射，发现交换 \((A_i,B_j)\) 的值以后变换出的序列贡献的逆序对一定与之相反，这个就是双射建立了。
但是这种结论真的是易观察的吗？我不好说。之后少看点题解先。
P10104
先记一类问题：集合划分容斥。
↑上面被注释了一大段。本来以为自己看懂了但是写着写着又不懂了。efi 说他懂，问他然后他跑去看贴吧了。放在这里吧，反正我看懂怎么做了，比赛的时候如果遇到了就闭着眼睛拍公式，拍出来不对再研究。
下午小测了两道计数，区分度离谱。切 T1 人很多，切 T2 人很多，交集为 2。
T1 的路径是暴力 DP 找性质优化；T2 的路径是是寻找方法刻画状态并容斥计数。
但是问题是 T1 也可以寻找方法刻画状态，搞出一个 \(\sum_a\prod_i\min(a_{i-1},a_i,a_{i+1})\) 状物，做不了一点；T2 也有神秘 DP 方法卡在三次方无法优化。
一再说明了拓宽思维的重要性。但是如何权衡各思考起点的时间分配也是个大问题，你根本不知道这棵树到叶子的链在哪个方向啊，启发式搜索的估价函数说白了就是对一个路径有没有前途的感知力。又有多少人有呢？
标签：归并,1.8,T2,T1,区间,日志,贡献,逆序 From： https://www.cnblogs.com/hagasei/p/18660711