《Alien DNA》..
这题就是直接倒过来模拟，关键是实现细节..对于每个位置，我们只要知道它是输入的某个位置，还是和前面某个位置相等即可，这样最后可以一遍推出答案。我们维护一个有K个位置的链表，每确定一个位置，就把它从链表中删去。这样我们每次只需要找到“待复制块”的起点和终点（终点下一个位置开始存放该块复制的结果）。这段确定后，可以将其删去。因此现在我们只需要快速定位。我们可以用数组模拟链表，并且再用两个数组表示每个位置的上一个和下一个。这样就能完成链表的功能，而不用真正删除。这样做的好处是，可以实现快速定位——因为操作数很小(5000个)，所以任何时候整个序列最多有5000段被删除的元素，也就是最多5001段连续的元素。因此对于每个操作，定位时可以暴力——沿着整个块走，最多5000步，走到最后不完整的块时，因为块内元素下标连续，所以不需要暴力扫描（实际上暴力扫描会退化。。因为块大小不是均匀的），直接下标加上去即可（这就是数组模拟链表的好处。。）任何时候定位都可以这么走。问题就解决了..

lz
写的是那个比较高端的做法并且比较意识流...反正我看不懂...
我写一下这题的另外一个做法吧
这题的要点在于,最终只需要前K个,因此在不断的复制的过程当中,下标超过K的可以直接扔掉.进一步地,假设第n次操作是[l,r],他将把[l,r]中的字符按照那个规则重新排列并插入到字符串当中,插入的字符的下标则是[r+1,2*r-l+1].我们令w为[r+1,2*r-l+1]和[1,K]这两个区间的交的长度,则最后一个操作对答案产生影响的,只有这w个字符,进而,我们只需要保存n-1次操作后的前K-w个字符就可以了(建议画图理解).这样不断地逆推回去,对于任意的i,我们都可以知道第i次操作实际对答案造成影响的长度,记为w[i].
在得到了这样的结论之后,我们就可以模拟了.因为实际有用的字符已经被我们事先确定了,因此模拟第i次操作时,一旦插入的字符数达到w[i]就立即停止.于是,实际的插入次数是O(K)的,就看怎么实现了.splay当然是可以的,当然常数要注意一下,需要实现按照那个乱七八糟的规则取出w[i]个字符,还有往splay里面插入一段字符.复杂度O(n+KlogK).