循环移动(cyclic)

问题描述
给出一个字符串S与N个操作。每个操作用三元组(L, R, K)进行描述：操作将字符串第L个到第R个位置构成的子串循环移动K次。一次循环移动就是将字符串最后的这个字符移动到第一位，其余的字符顺次后移。
例如，对于字符串abacaba，操作(L=3, R=6, K=1)后得到的字符串即为abbacaa。
求出在N个操作后得到的字符串。

输入格式(cyclic.in)
第一行一个字符串S。
第二行一个整数N，代表操作的总数。
接下来N行每行三个数L,R,K，每行代表一个操作。

输出格式(cyclic.out)
一行一个字符串，代表N个操作后的字符串。

样例输入
abbacaa
2
3 6 1
1 4 2

样例输出
ababaca

数据范围与约束
设|S|为字符串S的长度。
对于30%的数据，|S|<=100, N<=100, K<=100
对于100%的数据，|S|<=10000, N<=300, K<=1000,000,1<=L<=R<=|S|

这个题一开始我看到数据范围想到了链表，调了好长时间才调过去ToT，后来才发现复杂度原来不是O(n*s)，而是直接模拟的O(3*n*s)！更糟糕的是，人家直接模拟的比我好不容易调出来的链表快啊！ToT
先贴一下链表的代码：

#include<iostream>//链表(代码好恶心) 
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<string> 
using namespace std;
char s[10009];
struct H{
    int f,t;
}b[10009];
int len,n;
int main()
{
    freopen("cyclic.in","r",stdin);
    freopen("cyclic.out","w",stdout);
    gets(s+1);
    len=strlen(s+1);
    scanf("%d",&n);
    for(int i=1;i<=len;i++)
    {
        b[i].f=i-1;
        b[i].t=i+1;
    }
    for(int i=1;i<=n;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        k=k%(r-l+1);
        int x;
        if(k)
        {
            for(x=1;b[x].f;x++);
            int l1,r1,k1,k2;
            for(int j=1;j<=r;j++)
            {
                if(j==l) l1=x;
                if(j==r) r1=x;
                if(j==r-k) k1=x;
                if(j==r-k+1) k2=x;
                x=b[x].t;
            }
            //注意细节:-( 
            b[b[r1].t].f=k1;
            b[k2].f=b[l1].f;
            b[b[l1].f].t=k2;
            b[k1].t=b[r1].t;
            b[r1].t=l1;
            b[l1].f=r1;
        }
    }
    int x;
    for(x=1;b[x].f;x++);
    printf("%c",s[x]);
    for(int i=1;i<=len-1;i++)
    {
        printf("%c",s[b[x].t]);
        x=b[x].t;
    }
    return 0;   
}

直接模拟：

#include<iostream>//直接模拟O(3*n*s) ，正好八次方嘛！
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
char s[10009],b[10009];
int n;
int main()
{
    freopen("cyclic.in","r",stdin);
    freopen("cyclic.out","w",stdout);
    cin>>s+1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        k%=(r-l+1);
        int t=0;
        for(int j=l;j<=(r-k);j++)
        {
            b[++t]=s[j];
        }
        int p=r-k;
        for(int j=l;j<=(l+k);j++)
        {
            s[j]=s[++p];
        }
        for(int j=1;j<=t;j++)
        {
            s[l+k+j-1]=b[j];
        }
    }
    cout<<s+1;
    return 0;
}