题目描述

小美的彩带是由一条长度为 $n$ 的彩带一直无限循环得到的, 彩带的每一个位置都有一个颜色, 用 $a_{i}$ 表示。因此当 $i>n$ 时, $a_{i}=a_{i-n}$ 。

小美每次会从左往后或从右往左剪一段长度为 $x$ 的彩带, 她想知道她每次剪下来的彩带有多少种颜色。

题目思路

首先需要注意的是题目是持续的裁剪，就是每个操作是在上一个操作的基础上进行的，由于彩带无限长，所以只需要维护左端点和右端点当前裁剪到的位置。

考虑离线，对于裁剪长度大于n的，直接输出总的颜色数量即可，对于长度在n以内的，需要通过维护左端点和右端点先预处理好对应的彩带区间，由于彩带是无限循环的，所以可能出现从右边再到左边，这里可以将原始的彩带扩充为原来的2倍长度，这样从右边到左边也可以看做是其中的连续部分。

将得到的彩带区间进行排序，此时彩带区间之间已经互不干扰了，因为在此前我们已经通过维护左右端点得到了持续裁剪的区间，只需要计算每个区间内不同颜色数量即可。这里可以使用树状数组在nlogn的时间下得到颜色数量，我们考虑维护每个颜色最早出现的位置，由于彩带区间排序了，所以区间的左端点是不断右移的，每次左端点移动的时候，就将其代表的颜色的位置抹去，加入和它相同颜色的下一个位置。此时对于每个区间只需要求出对应区间的位置内包含了最早出现的颜色的位置的数量即可。

最后将离线排序后的区间对应的答案依次输出即可。时间复杂度为O(nlogn)。