[Ynoi2011] WBLT

时间大概在学科夏令营那段时间： 当时信息组的其他几个还有新高二的同学都开始学splay了，每天听到zms和yjq（一个学长，很强）讨论splay，还戏称为"spaly"，就感觉很紧张，他们怎么学这么厉害的东西，我还完全不了解。 然后我上网查了查splay，看到几百行的代码，看到什么zig，zag，势能分析（所以说写的这么丑的博客为什么会排前几），就感觉这个东西无法理解，大概看了看也没看懂。 去问了问于神splay的功能是什么——“插入，删除，查询第k小” 反正天天也无聊，于是就想了想： 线段树可以查第k小，只需要让其叶子sorted即可。 所以线段树是不是也能做？ 但是我们的线段树是一个静态的结构（当时的想法），这个东西要动态化才行，不然如何插入删除？ 线段树维护了每个点的区间，这个东西是静态的，也就是问题所在，我们考虑如何动态化这个东西： 插入一个节点的时候，如果找到了插入位置，那么一定是一个叶子，我们可以给这个节点新建两个叶子的儿子。 可以发现这个插入位置后面的所有节点都进行了平移，于是我们可以考虑对这个进行打标记来维护，称为平移标记，每次push_down平移标记来实现动态化。 每次删除的时候可以使用其兄弟来代替被删除的节点，同理需要进行平移标记的维护。 查询的时候先push_down平移标记，然后考虑是否进入左儿子即可。 可以发现这样的结构在插入链式数据下复杂度会有问题，考虑如何平衡。 我当时第一个想到的是设定一个ratio，使得左右儿子的比例在ratio之内，否则暴力重构，写了写发现好像是对的，去问于神，然后他说这个就是“替罪羊树”...... 诶所以我自己发明平衡树了？ 这么看来平衡树很简单啊。 这么看来我很强啊（错觉）。 然后我就一直按这个思路想下去了，想了很多种奇怪的写法，比如不平衡的时候合并一下，或者按中点分裂什么的。 我乱写了一个策略，通过了平衡树模板题，但是当时写的非常复杂，因为我维护了父亲，而且写法未经过优化。 后来发现不需要所谓的平移标记，可以直接维护size，这样可以按相对位置二分下去，减少了很多代码量。 发现可以不存father，减少了很多代码量。 又发现这个树也是可以”旋转“的，我们将旋转定义为合并两个节点即可（所以我看到说什么”无旋treap不用旋转，和treap不一样“的言论都感觉很谔谔，因为本身就是等价操作，同一个东西写出来不一样而已）。 同时也是可以分裂的，这里我分裂定义为了经过 $O( logn )$ 次旋转使得根的左儿子的右儿子是我们需要的区间。 我发现我设计出的平衡树的确是可以支持所有操作的，复杂度也都是 $O( logn )$ ，而且个人认为这个很好写。 所以我发明平衡树了？ 当时起了个名字“自平衡线段树”——“Self Balancing Segment Tree”，虽然后来查了很久发现其实是把两个OI界中未引入的东西结合在了一起，应该叫做“Weight Balanced Leafy Tree” 刚做出来的时候觉得这个是很重要的东西，于是对其他人都藏着掖着，生怕同学们学到我的技术，因为我当时也知道，省队就5个名额，同学都是我的竞争对手。 当时mhy听说我的平衡树很强，就问我能不能10分钟写出来，我接受了挑战，然后还真的写出来了，得到了集训队爷的认可+1 当时就对自己充满了自信，我都能发明这么强的一个数据结构，那进集训队保送清华北大还不是随手的事情吗（flag）。 【记得配图，WBLT的】 由于这是Ynoi，不是出题人拿来写装逼的文字的地方，所以你需要做一个数据结构题：

给你一个长为 $n$ 的序列，有 $m$ 次查询操作。 每次查询操作给定参数 $l,r,b$，需输出最大的 $x$，使得存在一个 $a$，满足 $0\leq a<b$，使得 $a,a+b,a+2b,\ldots,a+(x-1)b$ 都在区间 $[l,r]$ 内至少出现过一次。 如果不存在 $[0,b-1]$ 内的数，则输出 $0$。

第一行一个整数 $n$。 第二行 $n$ 个整数表示这个序列。 第三行一个整数 $m$。 之后 $m$ 行，每行三个整数 $l,r,b$，表示一次查询操作。

对于每个查询操作，输出一行一个整数表示答案。

6
1 1 4 5 1 4
3
1 6 1
2 3 3
3 4 1

0
2
0

Idea：nzhtl1477，Solution：nzhtl1477，Code：ccz181078，Data：ccz181078&Forever_Pursuit 对于 $30\%$ 的数据，所有出现过的数在 $[0,1000]$ 之间。 对于另外 $30\%$ 的数据，$b \leq 1000$。 对于 $100\%$ 的数据，所有出现过的数在 $[0,10^5]$ 之间。