题解 | #牛牛的猜球游戏#

题目链接：https://ac.nowcoder.com/acm/contest/19483/F
简要题意：给出一个长为10的数组，其中仅含0-9且每个数恰好出现一次。给出一个操作集，每次操作可以调换两个数。现在仅针对集合中[l,r]的一小段进行操作，求操作结果
这里采用的是广义前缀和的思想，当连续的操作产生某个叠加影响时，这种影响可以通过某种反向操作进行撤销。
我们假设第i次操作后状态为a[i]，初状态为a[0]，经过一系列操作后变成状态B，再经一系列操作后变状态A。
如下图，a[0]={1,2,3}经转换先变成B={3,1,2}，再变成A={x,y,z}。

下面考虑的问题就是，如何在A中抵消掉从a[0]走到B的所有操作？
观察可知，如果B要转回a[0]，第1位的数字3需要放回第3位，第2位的数字1需要放回第1位，第3位的数字2需要放回第2位。
也就是说，对于任何一种状态A，只需把第1位的数字放回第3位，第2位的数字放回第1位，第3位的数字放回第2位，即变成{y,z,x}，就能抵消掉a[0]到B的交换作用
所以，我们可以用tmp数组记录B的每个位置需要放回的位置，如本例就是tmp[1]=3,tmp[2]=1,tmp[3]=2.这样的话，tmp就完成了从状态B到a[0]的位置映射。
接下来只需要把tmp的映射作用于A，就能得到结果啦。
代码如下：

#include <bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
int a[100010][10];
int tmp[10];
int ans[10];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    _for(i,0,9)    a[0][i]=i;//初始化
    _for(i,1,n){
        memcpy(a[i],a[i-1],sizeof(a[i-1]));//复制上一次的结果
        int x,y;
        scanf("%d %d",&x,&y);
        swap(a[i][x],a[i][y]);
    }
    while(m--){
        int x,y;
        scanf("%d %d",&x,&y);
        _for(i,0,9)    tmp[a[x-1][i]]=i;//得到从状态x-1回到初状态的映射函数
        _for(i,0,9)    ans[i]=tmp[a[y][i]];//将映射函数作用于状态y
        _for(i,0,9)    printf("%d%c",ans[i]," \n"[i==9]);
    }
    return 0;
}