2019 ECNU XCPC March Selection 3

十分抱歉由于出题人的弱智操作导致今天大家体验十分不佳，给大家说声对不起。。。D题由于是改编的题目，特殊情况$w=t$出题和验题的时候考虑不周。A,G导入题面出现严重问题，导致大家心态爆炸。为了尽量减少大家的损失，最后计算积分的公式会减去一两次最差的情况，剩下的取平均值，并且相比过题数，罚时的影响很小。

A. A Hard Problem

在树链剖分（一种将树上节点离散化到一个数列上的一种预处理）的基础上，离线操作，枚举每个操作的值$x$。若该节点数值为$x$，则数值为$1$，也就是权值线段树/树状数组去搞。枚举值会导致复杂度变成$O(mn)$？，不要每次清空数组，而是单个单个撤销操作使得线段树回到初始状态，这样复杂度就是$O(mlogn)$了。

B. Building Bridge

为了方便描述将河左边的地点依次为$a_1, a_2...$，右边也一样。$dp[i]$表示右边最后一个被选择的是$b_i$，每次枚举新加的边连接的是左边的$a_i$，也就是$i$从小到大枚举，由于权值是一个排列所以右边可以连接的边只有十个不到，枚举右边可行的$j$，从$1..j-1$中选出一个$dp[k]$最大的$k$，这个可以使用线段树解决，让$i$和$j$相连。由于上一个连接点对$m,n$满足$m<i, n<j$，所以$(m,n)$不会和$(i,j)$相连。更新$dp[j]$的同时更新答案。复杂度$O(nlogn)$。

C. Choose a permutation

想到$3n$和$7n+1$的奇偶性不同就差不多要想到解法了。对于每次交换$(a_i, a_j)$。会被影响的逆序对有$(a_i, a_{i+1...j-1})$或者$(a_{i+1...j-1}, a_{j})$或者$(a_i,a_j)$。注意到$a_i$各不相同，最终分类讨论$a_{i+1...j-1}$与$a_i,a_j$的大小关系，可以得出每次交换一定会改变奇偶性。剩下的就是统计逆序对了，可以使用树状数组/归并排序$O(nlogn)$解决。

E. Easy simulation

十分抱歉这道题由于出题人的疏忽（弱智）没有检查到体面数据范围的错误，给大家非常差的体验，在这里道歉了。

用set维护在内存中的数据。节点应该包含该数据的值，该数据被读入的次数和该数据被加入的时间。按题目要求重载好小于号，就可以来模拟了。对于第一个操作，删除原来的节点，将读入次数加一在加进去新的节点。对于第二个操作，加入新的节点。对于第三个操作，弹出set中最小的那个节点所代表的数据，再加入新的节点。需要对数据的值进行离散化。

F. Funny chess

先讨论如何最少排在一起。首先最优解的棋子区间左端点一定原来就有棋子占用，否则将左端点后第一个棋子作为起点一定优于或等于左端点原来没放上棋子的方案。枚举每个棋子作为左端点，已经放在区间内的棋子可以不用动了，剩下就是每次操作放一个棋子到区间中（优先放端点，放完就一定能行了）。这样每次操作就能使得出现在正确位置的棋子数量加一，一定是最优的（又不能一次放两个棋子）。注意讨论非法的情况，就是最后一个棋子在区间右端点的左边，这样是无法摆出区间的。还有一种特殊情况，就是刚好只有一个长度大于2的空区间，一边是连续的一段，一边是左端点或右端点。这个时候是无法移动单个的那个端点的，但是可以移动另一边的端点到这边，正好空出一个格子，再把另一个端点放进去，两次完成。

再来讨论如何最多排在一起。考虑最左的棋子和最右的棋子，无论怎么走最少也会使他们的距离差减一。只要能够使得左端或者右端的两个或多个棋子相邻，就能将一端的棋子移到另一端，就能造成每次距离减一的理想情况了。那么只需考虑移动$(a_0,a_1)$区间还是$(a_{n-2},a_{n-1})$区间，只需要牺牲一个区间的距离就够了，选数值小的哪个就行了。

G. Glider

固定起点，能飞的距离就是高度减去够得着的上升气流的距离和。高度是固定的，肯定要让够得着的上升气流最多，那么肯定是在某个上升气流的左端点起飞。枚举起点，然后用前缀和+二分搞出答案。也可以使用更快的双指针，但是如果每次更新起点从头开始更新末指针，最坏复杂度就为$O(n^2)$。

H. H

$n+k | k+1, k=1..s-1$意味着$n-1|k+1, k=1..s-1$，这样被除数就固定了。$n-1$刚好到$k+1$不能整除，就是容斥搞一下，1到s都能被整除的数减去1到s+1都能被整除的数，除最小公倍数就行了。

最后的公式如下： $P(s,N)=\frac{N-2}{lcm(1,..,s)} - \frac{N-2}{lcm(1,...s+1)}$