Flandre Scarlet's Blog

大家纷纷AK，出题人受到打击；大家来月再战思考难度大战！

T1

一句话题意：给定平面上n个点，两个点之间有连线当且仅当一个点所在的“格子”处在另一个点所在“格子”的左下角。求所有连线（曼哈顿）距离的平均值。

30%：[tex]O(n^2)[/tex]暴力

60%：[tex]O(nlogn)[/tex]数据结构大力维护（加点、二维数点）

100%：发现题中坐标范围是[0,20)，这样所有点都分布在20*20=400个格子中。统计出每个方块中的点数和他们到方块左下角的距离总和，这样统计完之后，枚举两个块，用乘法原理计算出这两格中的点连成的所有路径总长。比暴力还好写。

T2

一句话题意：
[tex]\sum_{x=L}^R\sum_{d|x}d^k[/tex]

1-5：

用快速幂，对于每个询问用[tex]\sqrt{n}[/tex]的算法处理[tex]\sum_{d|n}d^k[/tex]，计算答案前缀和。

6-7：

去掉前缀和。

8-12：

枚举上式的[tex]d[/tex]，用调和级数的姿势求贡献[tex]O(nlogn)[/tex]

13-15：

送给不知道在想什么的人

[tex]\sum_{x=L}^R\sum_{d|x}d^k=\sum_{d=1}^nd^k\lfloor\frac{n}{d}\rfloor[/tex]

发现[tex]d^k[/tex]是完全积性函数，可以线性筛，那么对于每个询问分块计算即可。复杂度[tex]O(n+Q\sqrt{n})[/tex]

16-20：

送给完全不知道在想什么的人

易证（脑补、目测、打表、经验表明……）[tex]\sum_{d|x}d^k[/tex]是个积性函数，只要在线性筛里简单维护一些幂次信息就可以做到[tex]O(n+Q)[/tex]了。

T3

一句话题意：给出m条树链，求k条树链使得交集非空，最小化（树链最大值-最小值）。

就是NOI2016Day2T1的无脑树上版。

很容易想到的是枚举每个点，记录覆盖这个点的树链的长度，然后滑动窗口式的更新答案

复杂度[tex]O(n^2logn)[/tex]，[tex]log[/tex]体现在求lca上。送了70分。

标算树链按长度排序后，用双指针维护一段某点覆盖次数>=k的树链区间，每次更新答案。结合树剖后线段树可以[tex]O(nlog^2n)[/tex]秒过。

T4

一句话题意：这还有什么好两句话的。。

按等级排序后[tex]O(n^2)[/tex]的LIS式DP十分简单，送了60分（常数太小233）。

似乎还有20分给[tex]O(nlogn)[/tex]的LIS。

标算就是CDQ分治，处理前一半的操作，计算对后一半的贡献，这里面可以归并，一半按照攻击力排序，一半按照力量排序，用树状数组维护DP贡献。复杂度[tex]O(nlog^2n)[/tex]，CDQ常数不会太大。

树套树一定也能做，看常数吧233【写完题解出题人发现CDQ被树套树艹飞，惨啊】