牛牛的猜球游戏

更好的阅读体验

考虑如何利用差分的思路，即知道起始状态和目标状态如何求出过程量

我们并不关心具体过程，只关心一步到位的过程，于是去找相对位置的位移即可，记录这组位移，再用一个原始序列去进行这样的位移即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e6 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct NODE {
    int l, r;
} dat[N];

int n, m, cnt, pos[N][10], vis[10];

bool cmp(NODE a, NODE b) {return a.l < b.r;}

int main() {
    n = read(); m = read();
    for (int i = 0; i < 10; i++) pos[0][i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 10; j++) pos[i][j] = pos[i - 1][j];
        int x = read(), y = read(); swap(pos[i][x], pos[i][y]);
    }
    for (int i = 1; i <= m; i++) {
        int l = read() - 1, r = read(); memset(vis, -1, sizeof(vis));
        for (int i = 0; i < 10; i++) pos[0][i] = i;
        for (int i = 0; i < 10; i++) {
            if (pos[l][i] != pos[r][i]) vis[pos[l][i]] = i;
        }
        for (int i = 0; i < 10; i++) {
            if (~vis[pos[r][i]]) pos[0][i] = vis[pos[r][i]];
        }
        for (int i = 0; i < 10; i++) printf("%d ", pos[0][i]); printf("\n");
    }
    return 0;
}