# 13805 - Professor Bear's Challenge

>author: Utin
###### tags: `string`

---

## Brief
需建表並加入時間參數q以免TLE
String Operation目前已知共有4種變化
13572 String Operations 1
13573 String Operations 2
13692 Aftermath’s Ideology
13805 Professor Bear’s Challenge

## Solution 0

#include <stdio.h>
#include <string.h>

long long Q;
char arr[1000001]; // input
char table[100001][26]; // alphabet table
long long op[100001][3]; // operation queue
long long shift[1000001]; // for operation 4

int main() {
    scanf("%s", arr);
    scanf("%lld", &Q);

    long long len = strlen(arr);

    for (long long i = 0; i < 26; i++) table[Q][i] = 'a' + i;

    // input
    for (long long q = 0; q < Q; q++) {
        scanf("%lld", &op[q][0]);
        if (op[q][0] == 1) {
            char temp1, temp2;
            scanf(" %c %c", &temp1, &temp2);
            op[q][1] = temp1;
            op[q][2] = temp2;
        }
        else if (op[q][0] == 2) {
            char temp;
            scanf("%lld %c", &op[q][1], &temp);
            op[q][2] = temp;
        }
        else if (op[q][0] == 3) {
            scanf("%lld %lld", &op[q][1], &op[q][2]);
        }
        else if (op[q][0] == 4) {
            scanf("%lld", &op[q][1]);
        }
    }

    // operation type 1
    for (long long q = Q-1; q >= 0; q--) {
        // update
        for (long long i = 0; i < 26; i++) {
            table[q][i] = table[q+1][i];
        }
        if (op[q][0] == 1) {
            table[q][op[q][1]-'a'] = table[q+1][op[q][2]-'a'];
        }
    }

    // operation type 4
    for (long long q = 0; q < Q; q++) {
        if (q != 0) shift[q] = shift[q-1];
        if (op[q][0] == 4) {
            shift[q] += op[q][1];
        }
    }

    for (long long q = 0; q < Q; q++) {
        // operation type 2
        if (op[q][0] == 2) {
            /* operation type 4 */
            int index = op[q][1] - shift[q];
            int temp = (-1 * index / len) + 1;
            index += len * temp;
            if (index >= len) index -= len;
            /********************/

            arr[index] = table[q][op[q][2]-'a'] - 32;
        }
        // operation type 3
        else if (op[q][0] == 3) {
            /* operation type 4 */
            int index1 = op[q][1] - shift[q];
            int index2 = op[q][2] - shift[q];
            int temp1 = (-1 * index1 / len) + 1;
            int temp2 = (-1 * index2 / len) + 1;
            index1 += len * temp1;
            index2 += len * temp2;
            if (index1 >= len) index1 -= len;
            if (index2 >= len) index2 -= len;
            /********************/

            char temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }
    }

    // output
    for (long long i = 0; i < len; i++) {
        /* operation type 4 */
        int index = i - shift[Q-1];
        int temp = (-1 * index / len) + 1;
        index += len * temp;
        if (index >= len) index -= len;
        /********************/

        if (arr[index] >= 'a') printf("%c", table[0][arr[index]-'a']);
        else printf("%c", arr[index] + 32);
    }
    printf("\n");
}
// By Utin

## Reference