https://ac.nowcoder.com/acm/contest/19483/F

这道题乍一看像是个找规律或者模拟题， 实质上其每次操作都是固定的

那么这样的题目要如何带入前缀和来思考呢

我们将每一次的操作的序列状态的改变看作一个量

然后拿这个量形成的数组做前缀和

为什么可以这么转化呢，因为前缀和问题有一个共性：

每次的“增量”不相互影响，区间“量”等于区间前后侧的“积累量”之差

具体到这道题就是：

我每次只是交换杯子的位置，我的“增”就是进行交换，我的“减”就是之前的“增”的逆运算

然后用一个数组去记录“增”的积累，保证每一次减去k~n的积累量时

我用1到n的积累量减去1到k的积累量，得到的是：

用初始序列，从1开始，依次做第1到第k次的移动操作，再做第k到第1次的逆操作（即全部抵消）

再做第k~第n此的移动操作

细节看代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int f[N][10],sum[10];
int main(){
    cin>>n>>m;
    for(int i=0;i<10;i++) f[0][i]=i;//初始序列为0~9
    for(int i=1;i<=n;i++){//记录1~n号操作的量
        int a,b;
        cin>>a>>b;
        for(int j=0;j<10;j++) f[i][j]=f[i-1][j];
        //当前序列为上一个序列进行交换的结果
        swap(f[i][a],f[i][b]);
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        for(int i=0;i<10;i++) sum[f[l-1][i]]=i;
        for(int i=0;i<10;i++) printf("%d ",sum[f[r][i]]);
        printf("\n");
        /*
        这里为什么可以这么写呢
        你把sum[]理解成我们前缀和求区间值的那个答案
        本来我们要求的是a[l]+a[l+1]+……+a[r-1]+a[r]
        但是要用前缀和我们可以简化为f[r]-f[l](f是a的前缀和数组)
        但是我们只有a[0]+a[1]+……+a[r-1]+a[r](即f[r][])
        -f[l]是什么呢，就是sum[],只是我们这里没有‘-’这个操作
        本题的“+”和“-”都是赋值操作，这里就需要读者自行理解了
        */
    }
    return 0;
}