「BZOJ3600」没有人的算术
题目链接题目大意$N$ 个数（一开始全是 $0$）和 $M$ 个询问：修改第 $i$ 个位置的值为 $a_i = pair(a_l,a_r)$。询问 $l \text{∼} r$ 中最大值的下标。$0 < \text{pair}$；两个 $\text{pair}$ 比较时先比第一维，再比第二维。$n \leq 10^5,m \leq 5*10^5$题解可以发现这个关系有传递性。于是我们...
题目链接题目大意$N$ 个数（一开始全是 $0$）和 $M$ 个询问：修改第 $i$ 个位置的值为 $a_i = pair(a_l,a_r)$。询问 $l \text{∼} r$ 中最大值的下标。$0 < \text{pair}$；两个 $\text{pair}$ 比较时先比第一维，再比第二维。$n \leq 10^5,m \leq 5*10^5$题解可以发现这个关系有传递性。于是我们...
题目链接题目大意要求你维护一棵树，支持以下操作询问 $(u,v)$ 两点之间的距离将 $v$ 的祖先变成它的 $k$ 级祖先询问深度为 $d$ 的点中最靠右的点是啥。每层一开始的位置关系在输入中给出 每次 $2$ 操作的时候默认插入到子节点中的最右边。题解学了个叫做维护括号序列的东西。。（不知道是不是叫ETT？）括号序列就是在这个点入栈和出栈的时候都记录一次，比如样例1的括号序列就是 12...
如何维护区间我们都知道平衡树是一种很神奇的东西，可以用于维护动态的序列总信息，但是如果想维护其中的某一个区间的信息，我们该怎么做好呢？我们考虑换一种维护方式：平衡树的结构不是按照节点的值的大小来进行建树，而是以这个节点在序列中的位置为关键字来维护。也就是说对于平衡树中任意一个节点 $x$ ，左子树中的元素永远在它前面，右子树的元素永远在它后面。显然一个区间可以对应一个子树，所以我们要使用能提...
题目链接题目大意是对于每种物品被划分到不同的组里会产生不同的贡献，求一种最大的划分（这里的划分是连续一段划分到一起），并且要动态维护这个东西。我们首先考虑静态如何做这个东西，显然我们可以设出一个极为暴力的状态：$f(l,r,i,j)$ 表示燃料 $[l,r]$ 使用区间 $[i,j]$ 内的工作状态能得到的最大价值，直接 $O(4^3)$ 枚举中间点暴力转移一下就可以了。但是我们还要支持插入...
之前我写的 平衡树学习笔记 大体介绍了一下两种平衡树。这里详细的介绍 Splay 。 主要是从代码层面详细介绍，默认读者已经掌握了基本原理。