T6 午枫的字符串修改
题目大意
给定一个初始串，有 qqq 次操作，求操作完之后的字符串。
解题思路
本题一共有两个操作，这里记第一种操作为 MMM ，第二种操作为 CCC 。
我们可以先考虑如果只有第一种操作 MMM 的话，我们可以用差分的思想完成对所有字符循环右移的移动量的记录。定义差分数组 ddd ，假设对区间 [l,r][l,r][l,r] 做一次 M(ti,x)M(t_i,x)M(ti ,x) 后，差分数组将进行以下变化：
d[l]=d[l]+xd[r+1]=d[r+1]−xd[l]=d[l]+x\\ d[r+1]=d[r+1]-x d[l]=d[l]+xd[r+1]=d[r+1]−x
最后用前缀和求出每一位的移动量即可得到最终的答案。
第一种操作我们用差分实现了，那么如果加上第二种操作，其实可以在第一种操作的基础上，记录整个字符串循环右移的偏移量 disdisdis 。假设做一次 C(s,x)C(s,x)C(s,x) 后，偏移量 dis=dis+xdis=dis+xdis=dis+x 。
此时如果再对区间 [l.r][l.r][l.r] 做一次 M(ti,x)M(t_i,x)M(ti ,x) 的话，由于进行的是循环右移的操作，那么我们实际的区间需要对区间左右端点减去偏移量 disdisdis ，此时就会出现越界的情况，我们需要对越界的情况进行额外的处理：
* 如果没有越界，差分数组 ddd 会进行以下变化：
d[l−dis]=d[l−dis]+xd[r−dis+1]=d[r−dis+1]−xd[l-dis]=d[l-dis]+x\\ d[r-dis+1]=d[r-dis+1]-x d[l−dis]=d[l−dis]+xd[r−dis+1]=d[r−dis+1]−x
* 如果左边界越界，有边界没越界，差分数组 ddd 会进行以下变化：
d[l−dis+n]=d[l−dis+n]+xd[n+1]=d[n+1]−xd[1]=d[1]+xd[r−dis+1]=d[r−dis+1]−xd[l-dis+n]=d[l-dis+n]+x\\ d[n+1]=d[n+1]-x\\ d[1]=d[1]+x\\ d[r-dis+1]=d[r-dis+1]-x d[l−dis+n]=d[l−dis+n]+xd[n+1]=d[n+1]−xd[1]=d[1]+xd[r−dis+1]=d[r−dis+1]−x
* 如果两个边界都越界了，差分数组 ddd 会进行以下变化：
d[l−dis+n]=d[l−dis+n]+xd[r−dis+n]=d[r−dis+1]−xd[l-dis+n]=d[l-dis+n]+x\\ d[r-dis+n]=d[r-dis+1]-x d[l−dis+n]=d[l−dis+n]+xd[r−dis+n]=d[r−dis+1]−x
在这个过程中，差分数组 ddd 记录的移动量可以保证在 262626 以内，因为 262626 为一个循环，所以在记录的过程中移动量可以直接对 262626 取模。同理，字符串整体的偏移量 disdisdis 可以保证在 nnn 以内。
最后对差分数组 ddd 做一次前缀和就能得到原串每个位置的移动量，对每个位置加上这个移动量即可得到每一位变化后的字母。最后输出的时候还要注意把偏移量 disdisdis 的影响考虑进去。
时间复杂度 O(q+n)O(q+n)O(q+n)
参考代码
