专题班前缀和练习题 - F - 牛牛的猜球游戏

要求 [L,R] 区间的运算，怎么在 O(1) 的时间内，利用 [1,R] 与 [1, L-1] 的结果算出来
A 思路：矩阵
这是 N 个杯子，N 个球，建立一个 N * N 的矩阵，每进行一次操作，杯子交换也好，球移动也好，就是进行一次矩阵乘法运算。所以不管运算多少次，只要记得 [1, L-1] 和 [1,R] 的操作。
乘 [1,R]， 除 [1, L-1]即可。当然，除在矩阵中，就是乘逆矩阵。矩阵代码会很麻烦。
B 思路：群论
把（0,1,2,3,4,5,6,7,8,9）想成一个圈
无论怎么换，都是在这个圈中对元素进行交换。找到某种方法，对区间 [1, L-1] 的操作取消即可。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 20;
int s[maxn][20], n, m, a, b, ans[20], tmp[20];

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    memset(s, 0, sizeof(s));
    for(int j = 0; j <= 9; j++)
        s[0][j] = j;
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &a, &b);
        for(int j = 0; j <= 9; j++)
            s[i][j] = s[i - 1][j];
        swap(s[i][a], s[i][b]);
    }
    for(int k = 1; k <= m; k++){
        scanf("%d%d", &a, &b);
        for(int l = 0; l <= 9; l++)
            tmp[s[a-1][l]] = l;
        for(int l = 0; l <= 9; l++)
            ans[l] = tmp[s[b][l]];
        for(int l = 0; l <= 9; l++)
            printf("%d%c", ans[l], l == 9 ? '\n': ' ');
    }
    return 0;
}


    for(int _ = 1; _ <= m; _++){
        scanf("%d%d", &a, &b);
        for(int j = 0; j <= 9; j++)
            for(int k = 0; k <= 9; k++)
                if (s[a - 1][j] == s[b][k]){
                    ans[k] = j;
                    break;
                }
        for(int l = 0; l <= 9; l++)
            printf("%d%c", ans[l], l == 9 ? '\n': ' ');
    }

第一种代码，就是说，去找还原。
第二种代码，就是暴力询问，在 [1, R] 之后，去找到 [L-1] 的杯子。
第二种可能好理解一些，但是多了一个常数级别。