题目大意

要求维护一个序列${ A_n }$，按照每$m$个元素为一块分成$frac{n}{m}$块，其中$m|n$，有$Q$个操作，包括以下两种。

• 将整个序列旋转$x$位
  • 将每一块里面的元素都旋转$x$位

  现在给出序列的最后状态，以及每一步操作，要求还原出最初的状态。

  $n, Q<=10^5$

  ---

  分析

  首先先弄清楚一些很重要的东西。
  把一个序列左转$x$位相当于把这个序列右转$(len-x)$位
  将一个序列右转$x$位$Longleftrightarrow$每一个数的位置标号$p_i=(p_i+x)mod len Longleftrightarrow$每一个位置对应原序列的编号$num_i=(num_i-x)mod len$
  弄懂这个东西非常重要，直接影响了做出这道题需要的时间。
  必须举个例子
  比如右转$x=5$位，序列长度$len=9$
  那么原本在第$1$位的数$B$跑到了第$((1+5)mod 9=6)$位。
  首位对应原来的第$(0-5)mod 9=4$位。

  接下来考虑不同的块之间的同一个位置，把它们称作一个“组”。我们发现无论是第一种操作或者第二种操作，组内元素都是不变的。而第二种操作只会改变组间的顺序（然而环上相对顺序不变），第一种操作也会改变组间顺序，也是环上相对顺序不变，我们不妨开一个变量$d_{grp}$表示第一个组的编号来维护组的顺序。

  然后第一种操作不仅仅改变了组间顺序，也会改变组内的顺序。至于组内顺序的改变，它也是环上相对顺序不变的。类比第一种操作的维护我们只需要分别给每个组维护一个$d_x$就好了。而我们对$d$进行修改必定是连续的一段，而对$d$数组的询问只在最后统计答案时发生，那么只需要维护一个增量数组，最后取前缀和就可以了。

  ---

  后记

  掌握住旋转的特性。
  先将模棱两可的式子写好，写对。

最后

以上就是缥缈可乐为你收集整理的【COCI 2012】Rotate题目大意分析后记的全部内容，希望文章能够帮你解决【COCI 2012】Rotate题目大意分析后记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。