RainAir
My OI Blog
RainAir


文章归档

Splay 学习笔记 · 续

之前我写的 平衡树学习笔记 大体介绍了一下两种平衡树。这里详细的介绍 Splay 。 主要是从代码层面详细介绍,默认读者已经掌握了基本原理。 Splay 代码详解 结构体定义 [crayon-5c951346ec845051940558/] $ch$ 指针指向这个节点的左右儿子,$val$ 表示该节点表示…

   191   2018-10-28 去围观

GSS 系列题目题解

记录一下本人目前会做的 GSS 系列题目。 目前已经完成 GSS1,GSS3,GSS4,GSS5。 GSS1 题目描述 求最大子段和,序列的值可能为负数。 其中长度 $\leq 50000$。 解题报告 线段树维护这个序列。 线段树中维护四个值:$sum,lans,rans,ans$,分别表示当前序列的和,…

   230   2018-10-11 去围观

[HEOI2016/TJOI2016]排序

题目描述 题目链接 对一个长度为 $n$ 的排列进行 $m$ 次如下操作: 将区间 $[l,r]$ 中的数字升序排序。 将区间 $[l,r]$ 中的数字降序排序 最后输出位置 $p$ 的数字。 其中 $1 \leq n,m \leq 10^5$ 解题报告 发现询问只有一组,我们可以考虑二分答案。 考…

   248   2018-10-11 去围观

Can you answer these queries III

题目描述 题目链接 给定一个长度为 $n$ 的序列 $a$,有 $q$ 个询问,询问有两种: 单点修改 给定一组 $L,R$,求 $$max{\Sigma_{i=l}^{r}a_i}(L\leq l \leq r \leq R)$$ 其中 $n,q \leq 50000$。 解题报告 这个有和,我们可以用线段树维护。 线段…

   234   2018-10-02 去围观

「SHOI2007」园丁的烦恼

题目描述 题目链接 平面上有 $n$ 个点 $(x_i, y_i)$,$m$ 次询问,每次询问为一个矩形内有多少点。 允许离线。 其中 $ n,m \leq 500000 $。 解题报告 首先这个东西显然可以二维前缀和来预处理。 具体来说就是设这个前缀和数组为 $S$,每次暴力预处理,暴力查询…

   199   2018-10-01 去围观
文章归档