题解、Writeup、游记和碎碎念
2017 年 1 月
最快的写法是：while 非递归+按秩合并+秩和 fa 记在一个数组上，当 N 较小时秩选用 size，当 N 较大时秩选用 depth。
当不方便非递归时可以写递归的。 inline 似乎没有明显优化。
给定一个长度为 n 的正整数数列 a[i]。
定义 2 个位置的 graze 值为两者位置差与数值差的和，即 graze(x,y)=|x-y|+|a[x]-a[y]|。
2 种操作（k 都是正整数）：
1.Modify x k：将第 x 个数的值修改为 k。
2.Query x k：询问有几个 i 满足 graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的 a[x]的 graze 值<=k 的对数。（某位置多次修改为同样的数值，按多次统计）
有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响，我们需要计算上述序列的复杂程度。
的值，这将作为我们评估密码复杂程度的一个部分。由于答案可能很大，你只需要给出答案对 10^9+61 取模的值即可。