文章

Splay 伸展树 by 蒟蒻 XZY 2017.12.28 -1. 注 以下用数组模拟链表，不用指针。 未说明的情况下定义的节点结构体为： struct N{int f,s[2],d,sz;}e[SIZE]; 其中 $f$为父节点编号，$s[0]$为左儿子，$s[1]$为右儿子，$d$为该节点的值 阅读更多…

1. 题目 BZOJ – 3323（权限题）：传送门=￣ω￣= LUOGU – 3278：传送门=￣ω￣= 2. 题解 可以说这题令我非常 angry。。。 其实不难，就一个 splay 区间加&区间乘，结果写我这么久！ 我屮艸芔茻，因为在学校写的时候思路被中断了，所 阅读更多…

1. 题目 BZOJ – 3110：传送门=￣ω￣= LUOGU – 3332：传送门=￣ω￣= 2. 题解 哈哈哈终于完美 AC 这题惹！ 整体二分就是吼哇 QvQ！ 有先决科技点：整体二分解决单点修改区间 kth 问题：传送门=￣ω￣= 上面那题是单点修改所以用的树状数组 阅读更多…

1. 题目 BZOJ – 1901（要权限号）：传送门=￣ω￣= LUOGU – 2617：传送门=￣ω￣= ZOJ – 2112（数据范围扩大&多组数据）：传送门=￣ω￣= 2. 题解 以前写过一个树套树的题解 QvQ：传送门=￣ω￣= 这次用整体二分做 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 这，，，是我写的第多少个区间 kth 问题的算法&代码了？？？ 列举一下 QvQ： 分块 二分套线段树 主席树 二分套线段树套 splay（资磁修改）整体二分 QvQ 痛苦不堪。 整体二分个人感觉就是二分答案の升级版。 一般的二分答案做这题的话，就 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 感觉就是 Dynamic Rankings 那题的加强版。 还是老样子搞个线段树套 splay 就行了，具体解法见我写的那个 Dynamic Rankings 的题解： 传送门=￣ω￣= PS：之前在 BZOJ 提交好多次都 WA 掉了，最后发现读入优化写错了（ 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 mmp 好久没碰到这么恶心的题目惹！ 因为不会整体二分&CDQ 分治，所以就写惹树套树。 怎么说呢=。= 此题树套树卡常 还卡空间，线段树需要动态开点 理论上要开 long long 但开了就 TLE=。= 所以，，，最好的解决方法是用 zkw 线段 阅读更多…

1. 题目 传送门=￣ω￣= 更新：突然发现 LUOGU 上有这题（LUOGU – 2617），可以木有权限号刷～传送门=￣ω￣= 题目大意： 给你一个序列，要求资磁两个操作： 将某一个位置的数字改变 询问一段区间内第 k 小的数字 操作数和序列长度均在 10000 的范围内，无多组数据 阅读更多…

1. 题目 传送门=￣ω￣= 题目大意： 给一个静态序列，再给出 n 个操作，每个操作为求一个区间内第 k 小的数字是多少 2. 题解 以前写过一个二分套线段树的题解：传送门=￣ω￣=（题目一样，就是那个有多组数据这个没有）那个复杂度是 $O(mlog_2^3n)$，比较慢 现在要讲的是主席树の做 阅读更多…

1. 题目 传送门=￣ω￣= 2. 题解 又用 STL 水了一题啊！呜呼！ 其实还是有点思维的，就是你要记得：之前留下来的区间必然不重叠！ 当读入一个新的预约时，不断查找已经存在的预约中 end 值大等于新预约 start 值，并且最接近该 start 值的预约，找到一个删除一个，直到不能删除为止。 阅读更多…