官方题解

T6 午枫的字符串修改

题目大意

给定一个初始串，有 $q$ 次操作，求操作完之后的字符串。

解题思路

本题一共有两个操作，这里记第一种操作为 $M$ ，第二种操作为 $C$ 。

我们可以先考虑如果只有第一种操作 $M$ 的话，我们可以用差分的思想完成对所有字符循环右移的移动量的记录。定义差分数组 $d$ ，假设对区间 $[l,r]$ 做一次 $M(t_i,x)$ 后，差分数组将进行以下变化：

$$d[l]=d[l]+x\\ d[r+1]=d[r+1]-x$$

最后用前缀和求出每一位的移动量即可得到最终的答案。

第一种操作我们用差分实现了，那么如果加上第二种操作，其实可以在第一种操作的基础上，记录整个字符串循环右移的偏移量 $dis$ 。假设做一次 $C(s,x)$ 后，偏移量 $dis=dis+x$ 。

此时如果再对区间 $[l.r]$ 做一次 $M(t_i,x)$ 的话，由于进行的是循环右移的操作，那么我们实际的区间需要对区间左右端点减去偏移量 $dis$ ，此时就会出现越界的情况，我们需要对越界的情况进行额外的处理：

• 如果没有越界，差分数组 $d$ 会进行以下变化：

$$d[l-dis]=d[l-dis]+x\\ d[r-dis+1]=d[r-dis+1]-x$$

• 如果左边界越界，有边界没越界，差分数组 $d$ 会进行以下变化：

$$d[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$ 会进行以下变化：

$$d[l-dis+n]=d[l-dis+n]+x\\ d[r-dis+n]=d[r-dis+1]-x$$

在这个过程中，差分数组 $d$ 记录的移动量可以保证在 $26$ 以内，因为 $26$ 为一个循环，所以在记录的过程中移动量可以直接对 $26$ 取模。同理，字符串整体的偏移量 $dis$ 可以保证在 $n$ 以内。

最后对差分数组 $d$ 做一次前缀和就能得到原串每个位置的移动量，对每个位置加上这个移动量即可得到每一位变化后的字母。最后输出的时候还要注意把偏移量 $dis$ 的影响考虑进去。

时间复杂度 $O(q+n)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n;cin>>n;
    string s;cin>>s;s=' '+s;
    
    int q;cin>>q;
    vector<int>d(n+2);
    int dis=0;
    while(q--){
        int op;cin>>op;
        if(op==1){
            int l,r,x;cin>>l>>r>>x;
            if(l-dis>=1){
                d[l-dis]+=x;
                d[r-dis+1]-=x;
            }
            else{
                if(r-dis>=1){
                    d[l-dis+n]+=x;
                    d[n+1]-=x;
                    d[1]+=x;
                    d[r-dis+1]-=x;
                }
                else{
                    d[l-dis+n]+=x;
                    d[r-dis+n+1]-=x;
                }
            }
        }
        else{
            int x;cin>>x;
            dis+=x;
            dis%=n;
        }
    }

    for(int i=1;i<=n;i++) d[i]+=d[i-1];
    for(int i=1;i<=n;i++){
        d[i]%=26;
        s[i]=(s[i]-'a'+d[i])%26+'a';
    }

    for(int i=n-dis+1;i<=n;i++) cout<<s[i];
    for(int i=1;i<=n-dis;i++) cout<<s[i];
}