题目描述
题解
考场打了一个60分暴力，还炸成50.
正解很妙，感觉再做一遍也想不到。将(n-1)看成(0)，(n)看成(1)，(n+1)看成2，这样题目就转化成：
一个长度为n的队列，每个位置上都有(0,1,2)三种高度，每n次操作就将一个位置上的第二排的点向右移动一位。
如果最后一位高度为2要特殊处理，因为这不仅仅是向后移一位，实际上是移动到2轮后的第一位，所以不妨将每一轮设为(n+1)个数，最后一位初始为1，这样就能解决问题。
然后就有一个简单自然的做法：观察到队列中的0一旦变成了1，就不会再变回来，同时一个在第二层游动的2会消失。所以不妨计算出每个0变成1的时间，将询问放到一起排序，每次变化更新队列，判断当前点前(frac xn)位的数的高度，然后就能算出当前点的高度。