要求 [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] 的杯子。
第二种可能好理解一些,但是多了一个常数级别。