# 12612 - Queries on a String
## 題解:
用暴力解的話會TLE，以下兩種方法時間複雜度都是O(n)。
方法1是用額外的陣列去記下字元，空間複雜是O(n)。
方法2是用變數記下要被取代的字元，空間複雜度是O(1)。
## Code:
### 方法1:

#include <stdio.h>
#define N 10000 + 5

char s[N], temp[N];

int main(){
    int m, l, r, k;
    scanf("%s%d", s, &m);
    while(m--){
        scanf("%d%d%d", &l, &r, &k);
        --l, --r; // 0-based
        int len = r - l + 1;
        k %= len;
        for(int i=l; i<=r; i++){
            int newPos = (i + k > r ? i + k - len : i + k);
            temp[newPos] = s[i];
        }
        for(int i=l; i<=r; i++)
            s[i] = temp[i];
    }
    printf("%s\n", s);
    return 0;
}

### 方法2:

#include <stdio.h>
#include <stdbool.h>
#define N 10000 + 5

int m, l, r, k;
char s[N];

int main(){
    scanf("%s%d", s, &m);
    while(m--){
        scanf("%d%d%d", &l, &r, &k);
        --l, --r; // 0-based
        int len = r - l + 1, count = 0;
        k %= len;
        for(int i=l; count<len; i++){
            int curPos = i;
            char cur = s[i];
            do{
                int newPos = (curPos + k > r ? curPos + k - len : curPos + k);
                char new = s[newPos];
                s[newPos] = cur;
                curPos = newPos;
                cur = new;
                count++;
            }while(i != curPos);
        }
    }
    printf("%s\n", s);
    return 0;
}

###### tags: `NTHUOJ`