F 牛牛的猜球游戏

我们可以用一个数组 记录下前 次操作后第 杯子里球的颜色，也可用一个 vector 存储。
那么每个询问 到 后的结果，我们可以对于每一个 找到对应的 ，这里的对应指杯子里球的颜色相等，并将 。

那么为什么呢？ 原因如下：

如果 那么就说明如果颜色 在第 号杯子里，那么无论如何经过 的操作后 都会出现在第 个杯子里。因为我们是从 操作开始的所以 。

my code(有点写麻烦了，但不想改了):

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n,m;
int a[maxn][20],l[maxn],r[maxn],res[20];
void solve(int x,int y){
    x--;
    for(int i = 1;i <= 10;i++)
    for(int j = 1;j <= 10;j++)
    if(a[x][i] == a[y][j]){
        res[j] = i - 1;
        break;
    }
    for(int i = 1;i <= 10;i++)
    printf("%d ",res[i]);
    puts("");
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)
    scanf("%d%d",&l[i],&r[i]);
    for(int i = 1;i <= 10;i++) a[0][i] = i;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= 10;j++)
        a[i][j] = a[i - 1][j];
        swap(a[i][l[i] + 1],a[i][r[i] + 1]);
    }
    int x,y;
    while(m--){
        scanf("%d%d",&x,&y);
        solve(x,y);
    }
    return 0;
}

std:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct ballList {
    int pos[10];
};
ballList operator - (const ballList A, const ballList B) {
    ballList C, temp;
    for (int i = 0; i < 10; ++i) {
        temp.pos[B.pos[i]] = i;
    }
    for (int i = 0; i < 10; ++i) {
        C.pos[i] = temp.pos[A.pos[i]];
    }
    return C;
}
ostream & operator << (ostream& os, const ballList &ob) {
    for (int i = 0; i < 10; ++i) {
        if (i)os << ' ';
        os << ob.pos[i];
    }
    return os;
}
ballList presum[MAXN];
int n, m, u[MAXN], v[MAXN], l, r;
ballList bf(int l, int r) {
    ballList ret;
    for (int i = 0; i < 10; ++i) {
        ret.pos[i] = i;
    }
    for (int i = l; i <= r; ++i) {
        swap(ret.pos[u[i]], ret.pos[v[i]]);
    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    for (int i = 0; i < 10; ++i) {
        presum->pos[i] = i;
    }
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> u[i] >> v[i];
        presum[i] = presum[i - 1];
        swap(presum[i].pos[u[i]], presum[i].pos[v[i]]);
    }
    for (int i = 1; i <= m; ++i) {
        cin >> l >> r;
        cout << presum[r] - presum[l - 1] << endl;
    }
    return 0;
}