T2牛牛的猜球游戏

题面

更好的阅读体验

记忆化+映射做的。

思路应该挺显然的，就是记忆化一下连续操作后的结果。

比如操作为：

1 2
2 3

的时候，我们可以直接记录两次操作后的数组为

1 2 0 3 4 5 6 7 8 9

也就是可以直接存一下第 次操作以后 ~ 序列的结果，空间是 ，看起来非常正解。但是题目要求的是 ~ 的。

联想前缀和、线段树等，我们很容易想到要用 ~ 的结果和 ~ 的结果做一些类似于 减法 的操作。

即考虑记录第 次操作的逆操作。

也就是假设第 次操作后的数组是 ~ 的顺序数组，反向映射得到操作前的数组，map或者直接普通数组都行。

为什么这样可以，其实道理很简单，最初的数组和现在的数组中的元素存在一一对应的关系，不要管里面的数字的大小关系的话，实际上就是 个不一样的符号经过若干次操作以后的某个排列顺序，把现在当成有序，那最初的就是逆操作的结果。

最后只需要相前缀和查询一样先把数组初始化为 ~ 的逆操作后的结果，再做一次 ~ 的操作就行了，其中 ~ 的操作中前 ~ 的操作会让数组变成 ~ 的顺序数组，之后的操作就是 ~ 的操作了。

code

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define per(i,a,b) for(int i = (a);i >= (b);--i) 
#define mkp std::make_pair
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
inline bool cmp(int x,int y){return x < y;}
/* -fsanitize=undefined */
const int N = 1e6+9;
const int inf = 1e9+9;
const double eps = 1e-7;
int _,n,m,a[2*N][15],b[2*N][15],u,v,opt[2*N][3],tmp[15],ans[15];
int map[10];
int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL //use "g++ xxx.cpp -DLOCAL"
        freopen("in.in", "r", stdin);
    #endif
    cin >> n >> m;
    rep(i,0,9) b[0][i] = a[0][i] = i;
    rep(i,1,n) cin >> opt[i][1] >> opt[i][2];
    //记忆化1~i的结果
    rep(i,1,n){
        rep(j,0,9) a[i][j] = a[i-1][j];
        u = opt[i][1] , v = opt[i][2];
        std::swap(a[i][u],a[i][v]);
    }
    //推出1~i的逆操作的结果
    rep(i,1,n){
        rep(j,0,9) map[ a[i][j] ] = j;
        rep(j,0,9) b[i][j] = map[j];
    }

    while(m--){
        cin >> u >> v;
        u--;//把l变成l-1
        rep(i,0,9) tmp[i] = b[u][i];
        rep(i,0,9) map[ i ] = a[v][i];
        rep(i,0,9) ans[i] = tmp[ map[i] ];
        rep(i,0,8) cout << ans[i] << " ";
        cout << ans[9] << "\n";
    }
    return 0;
}