Day1

· · 个人记录

Treap：

除了标准BST外，维护随机权值，满足大根堆的性质。

插入：若已有节点，累加计数器，否则找到空位置新建节点，并通过左/右单旋来满足堆性质。

删除：先找到要删的点，若cnt大于1，计数器减一，否则将当前节点向儿子单旋，直到该点只剩不多于一个儿子，这时直接删掉，将儿子放在当前位置。至于是和左儿子还是右儿子旋转，看它们的随机权值。若左大于右，和左儿子转，否则和右儿子。易知这满足堆的性质。

若要支持序列分裂、合并：

分裂：将分裂的两棵树设为T1,T2。先递归分裂当前点的子树，若分裂的点在左子树，将当前点左儿子设为T2，右儿子不变，以当前点作为T2，原T1不变。右子树同理。注意以叶子作为终止条件。

合并：递归合并编号小的区间的右子树，编号大的区间即可。然后合并完的树作为新的右子树。

这里的插入和删除就可以通过这两种操作暴力解决了。

这种Treap又名FHQ Treap，常数比普通Treap差一些，码量相较则少不少。

Splay：

双旋。若三点是同一种关系（直链），先转父亲后转儿子。否则如果是折链，转完儿子转父亲。

操作完之后将其旋到根节点即可。

分裂/合并都十分简单，不写了。

但是这玩意常数不小，卡常题还是老老实实写点常数小的平衡树吧(红黑树(×)/普通Treap(√))

Upd：另外还有01trie在空间允许的情况下也可以当平衡树使。时间常数也较为优秀。而且还有树状数组当成平衡树使的骚操作。但是01trie的复杂度是 O(n \log v)，其中 v 是值域，所以在值域很大的情况下可以选择牺牲一部分常数换取写法简单，或者在不强制在线的情况下先离散化再做。

注意：

平衡树的很多操作的维护方法和线段树十分类似，平衡树优势在于平衡树可以动态维护，且支持翻转操作，而线段树相较之下比较好写。

P4198 楼房重建：

线段树。每个区间维护答案和max。

对于区间A和区间B的合并，设区间B的左右子区间分别为C,D。

若Amax<=Cmax，显然A对D并无影响，将D答案直接加上后，递归计算A，C答案即可。注意这个D答案是整段区间中统计的所以需要许多细节！！！

若Amax>Cmax，显然C答案已经为0，直接递归计算A，D答案即可。

容易看出复杂度是 O(n\log^2n)。

P5278：

多个线段树+区间gcd+平衡树。

区间判断是否为公差k的等差数列，维护3个东西，区间gcd，区间min/max，以及区间最大pre。

显然一个区间满足题目要求，仅当这段区间相邻数的差的gcd为k，且区间中没有重复的数，最大值和最小值的差为k*(r-l)。

显然差可以通过线段树维护min/max知道，区间gcd也可以轻松跑出，那么就是如何求重复了。

维护一个数组pre表示编号小于自己，且最接近自己的颜色相同的点的编号，那么显然区间 [l,r] 没有重复，当且仅当其最大的pre都小于l。

那么只需要处理出pre之后维护区间最大pre即可。这还是线段树。

pre在修改的时候用类似链表的插入/删除方式就可以解决了。

这里还要维护一下相同权值的点的平衡树进行查找。

P3215：

数据保证有解，所以查询的区间长度一定是偶数。

设左括号为1，右括号为-1

首先一个结论，查询的答案是 |最小前缀和|/2(上取整)+最大后缀和/2(下取整)。(因为有长度为偶数的保证)

操作有许多种，显然平衡树才能满足需要。

于是类似于线段树，维护几个东西：区间和，区间最大/最小前缀和/后缀和。

然后显然区间合并时候，区间和直接加就行，剩下的利用GSS1的做法，可以轻松合并。

对于区间赋值操作，信息更新十分简单，不说了。

区间（序列）翻转操作，直接用平衡树的翻转标记即可。

区间（括号）翻转操作，将对应区间的前缀信息和后缀信息调换一下即可。

P4097：

是李超线段树，接近模板，有时间就去看看。

lxl：我瞎yy的题

题意：给定序列，两种操作：区间修改矩阵，区间从左往右求矩阵乘积。

矩阵是3*3的，要求复杂度除了常数只能有一个log。

做法：建树按 [1,2^k] 个点建，显然每一个子节点的大小都是二的整数次方幂。这样，我们修改时遇到一个新的矩阵时，直接自乘自预处理出所有该矩阵的 2^i 幂，然后区间修改的时候对于整块包含在内的区间用预处理的值带入即可，合并时用矩阵乘法即可。

复杂度 O(27n \log n)

CF453E(3100pts)

题意：序列每个位置有初值 a_i，每秒增加 r_i，每个位置有上限 m_i，每次询问给定时间，求一个区间所有位置的值之和，同时将所有值归零。询问和序列长度1e5级别。时间在1e9。询问的时间递增。

十分诡异的做法/jk

首先初始权值需要特判一下并做细节处理。

看到查询，两种操作是一起的。从这里入手，可以使用set/平衡树维护合并和分裂，则每次我们对一整段操作查询，就分别对于每一段裂开的区间进行查询，然后将整部分合并，并将这一段的左和右边分裂开。

通过均摊证明，这样，分裂和合并的次数是 O(n+m) 的，这部分的复杂度是 O(n \log n) 的，而且查询的区间个数也是 O(n) 级别的。

然后询问就转化成了求一段（上次操作时间相同）的连续区间的经过 x 时间后的值之和。

然后询问可以看成二位数点，可以利用扫描线解决。

似乎细节特别多的样子/fad

注：

下面开始是一种数据结构的套路：利用题目中给定的奇怪限制（注意操作的特殊性质，题目中给出的特殊限制条件，或者某个小的诡异的数据范围），将区间中实际进行操作的个数计算出来（一般为 n \log n），然后用这点特殊性质进行维护和计算。

一般来说，这种操作的暴力计算方法就是用线段树维护区间的某种信息（很多时候是max/min），然后用这种信息判断区间中是否有操作点，有就递归搜索并操作，否则不作处理。

CF438D(2300pts)：

查询/序列1e5，值域1e9，要求支持单点修改，区间求和，区间取模，模数每次给出。

线段树维护区间max。如果当前区间max大于模数，递归看左右子区间的max是否大于模数，递归处理大于的部分。不大于退出即可。

因为每个数最多被取模log次，其它时候值不变，所以复杂度 O(n \log^2 n)。

CF702F(2800pts)：

有 n 种T恤，每种有价格 c_i 和品质 q_i。

有 m 个人要买T恤，第 i 个人有 v_i 元，每人每次都会买一件能买得起的 q_i 最大的T恤。一个人只能买一种T恤一件，所有人之间都是独立的。

问最后每个人买了多少件T恤？如果有多个 q_i 最大的T恤，会从价格低的开始买。

转变一下，其实要求的就是给定人，然后将物品按q排序后，从前往后看每一个物品，求所有v大于c的人，将其v减去c，并将cnt加1。

然后又是类似的折半思路，我们对人按照钱数建立平衡树，然后对于一个物品的价值设为x，然后我们在树上二分找到价值在 [x,2x] 的物品，对于这一部分暴力减钱数并累加计数器，然后 (2x,+∞) 的部分直接打上区间钱数减，计数器加的标记即可。

最后将价值在 [x,2x] 的人，大于2x的人，小于x的人分裂成3棵平衡树，然后操作完后合并起来三部分即可。

用上一题的折半思想，容易看出这部分的复杂度是 O(n\log^2n)。

还有一堆Ynoi不想记了。。有时间看看能不能口胡一下吧。。