[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$,表示一次查询操作。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

0
2
0

说明

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