特别行动队 考点：斜率优化 题意：有个正整数，请分成若干段，每段的总和为，价值为，求最大总价值。。 考虑动态规划，表示前个队员产生的最大价值，则显然 最终答案为，利用前缀和可以实现求，时间复杂度。 考虑到瓶颈主要在于状态转移时，最佳状态无法快速找到，所以尝试斜率优化。 观察转移方程： 经过展开、移项可以化为： 然后一眼就可以看出来，这个式子有点类似直线的表达式： 当我们选定时，显然确定了，并且越小，越小。那么把这个问题放在平面上，就是确定了直线的斜率，且直线必须经过某个定点，最小化它的斜率。 注意到是负数，也就是单调递减且始终为负，而且，那么这是斜率优化的经典模型，时间复杂度优化到。 总...

Nowcoder小白月赛12题解 更新：2019.3.11在本文末尾补充了标程链接~ 命题：fzszkl 前言 月月和华华是出题人的好朋友，然后他们最近（2019年2月份）互相帮助对方脱单了，出了这套题祝他们幸福。 第一题 考虑贪心，将所有区间按照左端点排序，从左往右遍历。用一个变量维护我们当前最远可以够到的右端点，然后枚举左端点不超过右端点+1的所有区间，选择右端点最靠右的一个即可。时间复杂度。 第二题 快速幂和快速乘的模板题，时间复杂度。 第三题 长得很吓人的送分题，注意到是一个完全积性函数，所以线筛即可。对于素数，直接快速幂。因为素数的个...

史上最简单的平衡树：无旋Treap 与下文无关的补充说明： 本文最早发布在牛客发帖区，链接https://ac.nowcoder.com/discuss/177864 ；最近因为牛客加入了博客功能就搬迁到了我自己的博客，pdf文件中未作修改。还有就是，撰写本文时迷恋英文符号……对于您阅读时产生的恶心在下深感抱歉233 作者:fzszkl 博客地址:https://blog.nowcoder.net/fzszkl 使用此PDF文件时请保留上述信息!谢谢合作!觉得文章不错请点击链接为博客点赞! 高能预警:所有示例代码都是数组版的,欢迎copy! 前置知识:线段树!请确保你完全理解最基础的线段树...

点分治？没听说过，还是写一发DSU On Tree（树上启发式合并）好了~ 个人拙见，DSU On Tree主要是解决一些静态的子树信息查询的问题，当然通过一些骚操作可以拓展。拓展到路径最常见的套路就是强制该路径经过当前子树根节点，然后DFS枚举每个点作为根节点。 点分治的思想主要是寻找重心作为根节点以优化复杂度，启发式的思想则类似树链剖分，每次计算贡献时先枚举轻儿子，计算后清除贡献，最后枚举重儿子，计算后保留重儿子的信息，最后依次枚举轻儿子，暴力将答案计入贡献。这样的复杂度是的。 然而只写这么多过不了审核，所以接下来仔细解释一下算法的原理！因为网上其他的教程都太简短了！所以我才学了一整天！ ...

史上最简单的平衡树——无旋Treap 作者:fzszkl 博客地址:https://ac.nowcoder.com/discuss/177864 使用此PDF文件时请保留上述信息!谢谢合作!觉得文章不错请点击链接为博客点赞! 高能预警:所有示例代码都是数组版的,欢迎copy! 前置知识:线段树!请确保你完全理解最基础的线段树和LazyTag(区间加法和区间求和). 一、简介 无旋Treap,又称fhq_treap,是范浩强大佬发明的一种强力数据结构. 总的来说,它可以支持一切Treap和Splay等平衡树的操作,支持可持久化(但是这篇博客不会讲),常数远小于Splay,但是处理LCT问题略比...

Nowcoder小白月赛12题解 更新：2019.3.11在本文末尾补充了标程链接~ 命题：fzszkl 前言 ***和华华是出题人的好朋友，然后他们最近（2019年2月份）互相帮助对方脱单了，只剩下了孤单寂寞的出题人一个人，出了这套题祝他们幸福。 （怎么可能哈哈哈哈哈，出题人当然也是有女朋友的。） 第一题 考虑贪心，将所有区间按照左端点排序，从左往右遍历。用一个变量维护我们当前最远可以够到的右端点，然后枚举左端点不超过右端点+1的所有区间，选择右端点最靠右的一个即可。时间复杂度。 第二题 快速幂和快速乘的模板题，时间复杂度。 ...