2016-12-26 06:00:00 ~ 2016-12-26 07:00:00
邀请码：8728 描述：高质量比赛，赛后提供题解。如果觉得本比赛太水/太垃圾，可以私信D出题人zhouyonglong，但请不要举报，谢谢！ 比赛时间：12月25日全日
难度：提高-/提高/提高+ 赛时答疑：洛谷私信zhouyonglong\QQ421738558 奖励：第一到三名且至少150分者分别可以获得5,3,1元的奖励，奖励发放仅支持支付宝/微信
题解： T1: 这题我们用归并排序统计逆序对。在进行归并排序时可以顺便记下每一层的翻转前和翻转后的逆序对数。如果我们假设1-2^n的为第一层，1-1、2-2、3-3……2^n-2^n的为第n层，那么对于一个询问q[i]，我们只需将此时1-q[i]层的当前的逆序对数翻转后的交换一下，再统计下每一层的当前逆序对数即可。 空间复杂度O(2^n) 时间复杂度O(2^nn+nm) T2: 这题很容易想到n^2的dp，设f[i]为从1到i能选取的sum最大值，那么
for (int j = 1 ; j<i ; j++)
if ( a[j] < a[i] ) f[i] = max( f[i] , f[j] + w[i] ）;为了在log n时间内完成这个步骤，我们考虑离散化a数组，然后用线段树维护dp即可 空间复杂度O(n) 时间复杂度O(T*n log n) T3: 这道题的重点在于对于一个点i，将sum的定义看成每种颜色对它的贡献，即为包括这种颜色的链的数量。 想清楚这个以后就是一个点分治了，将子树两两之间的贡献处理清楚即可 空间复杂度O(n) 时间复杂度O(n log n)
有需求的可以找我要代码