T1：太陽の傾いたこの世界で（Version1）

Idea：ccz Solution：ccz Std：ccz Data：ccz

https://www.luogu.org/problem/P5062

维护一棵红黑树（题意指的是对应2-3-4树的红黑树），可以发现每次插入后至多发生两次旋转。

旋转发生的情况是：一个黑点的孩子为一红一黑，但红色孩子有一个孩子为红色，此时视情况单旋或双旋。

不旋转而只调整颜色的情况是：一个黑点的左右孩子都是红色，且左右孩子中有一个有红色的孩子，此时将黑点的孩子设为黑色，黑点设为红色，继续考虑是否有两个红点是父子。

如果一个点的左或右孩子为空，那么有一个区间内的数插入后会在这个空位上，同时每个数也对应了一个空位，于是可以从空位开始，自底向上利用红黑树的结构和性质计算旋转次数。

对每个黑点，记录有几个数插入到子树中可以使黑点变红；

对每个红点，分别记录左右孩子变红的方案数（考虑左右孩子为黑点和为空的情况）；

对每个点，记录子树中插入一个数，在子树内造成的旋转次数；

维护了这些信息，可以在插入时在根维护全局的答案。

查询的是分别插入$[1,x]$内的整数造成的旋转次数，只要找出x对应的空位，将这个空位到根的路径的答案重新计算，不考虑大于x的数的贡献，就得到了答案。

总时间复杂度$O( mlogn )$，空间复杂度$O( n + m )$

对这题的评价：3/11

T2：空の上の森の中の（Version1）

Idea：zcy Solution：lxl Std：lxl Data：lxl

https://www.luogu.org/problem/P5063

可以证明这个线段树只有$O( logn )$种不同大小的节点

对于每种节点大小分层，维护一个数据结构，支持：

1.区间加

2.单点修改

3.区间rank

这个是一个经典问题，目前离线上界是$O( m \sqrt n )$，在线上界是$O( m \sqrt {nloglogn} )$，我们通过一些规约证明了这个问题不弱于一个$\sqrt n \times \sqrt n$的矩阵乘法，所以目前认为难以达到$O( n \times polylogn )$的复杂度

可以证明线段树的每层只有$O(1)$种不同大小的节点，那么我们的总时间复杂度是

$O( m \sqrt n + m \sqrt {n/2} + m \sqrt {n/4} + ... )$ = $O( m \sqrt n )$

空间复杂度可以通过一些trick做到$O( n + m )$

对这题的评价：3/11

T3：この戦いが終わったら（Version3）

Idea：lxl Solution：shadowice1984 Std：shadowice1984 Data：lxl

https://www.luogu.org/problem/P5064

考虑值域分块，查询kth的时候先在值域分块上面找到kth属于哪个块，然后枚举块内元素即可

枚举块内元素时，即查询一个值是否在一个时刻属于一个连通块，在这个题里面由于支持撤销，所以需要使用时间复杂度$O( logn )$的按秩合并并查集，这部分是平凡的

然后考虑如何找到kth属于哪个块，一个简单粗暴的思路是并查集上每个点维护一个长度为$O( \sqrt {nlogn} )$的数组，即值域分块的数组，然后合并两个点的时候暴力把两个数组相加，这样我们就可以求kth了

这样空间复杂度是$O( n \sqrt {nlogn} )$的，会MLE，考虑如何优化空间复杂度

如果我们使用按size合并的并查集的话，可以发现这个并查集的树高是$O( logn )$级别的

可以发现我们每个连通块如果开一个数组来维护值域分块结构很浪费，因为对于小的连通块这个分块结构是非常不满的，而大的连通块个数很少

所以如果我们把数组换成一个有序的链表，即用链表来维护这个值域分块，此时我们的空间复杂度将会骤降至$O( nlogn )$

具体点来讲我们在并查集上每个节点维护一个链表，即启发式合并这个值域分块的链表，这里链表中的节点上存一个二元组$(id,cnt)$表示这个集合中有cnt个属于编号为id的值域块的点,查kth的时候for一遍这个有序的链表就可以了

如此这般分析的话我们会发现一个节点的链表size为$\min(size(p),\sqrt n))$

简单分析一下空间复杂度就是$O( nlogn )$的，因为每一个点最坏情况下会在每个祖先处被存储一次

然后考虑一下完全可持久化带来的影响

先将所有操作的版本树建出来，然后我们可以通过在版本树上面DFS来实现题目中的所有操作

每次撤销一个合并操作的时候，可以通过将两个值域分块的链表相减来实现，这个的时间复杂度还是$O( \sqrt {nlogn} )$的

总时间复杂度$O( m \sqrt { nlogn } )$，空间复杂度$O( nlogn + m )$

考虑怎么去掉log，并查集的这个log可以对原树进行分块之后加一些trick来去掉，空间的这个log可以通过逐块处理来去掉

总时间复杂度$O( m \sqrt n )$，空间复杂度$O( n + m )$

对这题的评价：4/11