简单题，赛时找到了$O(1)$查询的规律于是切了。
从倍增LCA那里借鉴了一点东西：先将a、b抬到同一高度，然后再一起往上爬。所用的步数$×2$就是了。
抬升到同一高度的过程中，如果高度不是d的整数倍，则必定有一步没有走满d个高度。
如果剩下的步数为偶数，则直接累计答案，可以证明没有更优的情况（~~虽然我懒并没有证明但我觉得这挺显然的啊……~~）
如果剩下的步数为奇数，考虑把原来没有走满的那一步走满，然后把多余的那一步补到下降中，也可以证明没有更优的情况。（~~显然……于是我就又弃坑证明~~）
怕是考场上只有我一个人敲了一遍splay /捂脸.jpg
一开始以为是个平衡树果题，然后就写了。最需要处理的那一部分被我一个sb的sort给干掉了。
正解单调栈+离散化+桶。
开一个单调栈维护序列，栈内单调递减。
顺序扫序列的每一个元素。push的时候记一下push前栈顶元素，即为该点左侧第一个比它大的值。该点被pop的时候记录一下是哪一个元素pop了它，即为该点右侧第一个比它大的
值。（注意记录的都是位置）
算出左侧的长度l和右侧的长度r，$l×r$即为该点在最终序列里面出现的次数。
然后开桶统计前缀和，实现$O(1)$查询。
至今不知道dp转移方程的意义。。。
于是听了某一个打表找规律赛时A掉的大神讲了一下规律……
先鸽了，回头自己推一下或者稍微问一下……
sb语文题，读了大概20分钟题。然而赛场上的代码各种错误于是完美爆零了。
正解sort+去重，累加答案的柿子题目都给出来了……
错误原因：
1.没注意输出格式冒号后面有一个空格
2.下面的东西显然不能处理出现0了的情况。
if(in_a[i]!=in_a[i-1]) a[++n]=in_a[i],sum[n]=1;
约瑟夫问题2改编题目。
结论：ans=(ans+i)%(n-i+1);
注意模数不一定是质数，crt就好
鸽了。
赛时乱搞A了。把k和所有的ai取一个gcd，在k内递增，每个都取出来就好。
原文：https://www.cnblogs.com/xingmi-weiyouni/p/11420888.html