F 牛牛的猜球游戏

我们可以用一个数组 $sum_{i,j}$ 记录下前 $i$ 次操作后第 $j$ 杯子里球的颜色，也可用一个 vector 存储。
那么每个询问 $l_i$ 到 $r_i$ 后的结果，我们可以对于每一个 $sum_{l-1,j}$ 找到对应的 $sum_{r,k}$ ，这里的对应指杯子里球的颜色相等，并将 $ans_k\leftarrow j$ 。

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

如果 $sum_{l-1,j}=sum_{r,k}$ 那么就说明如果颜色 $p$ 在第 $j$ 号杯子里，那么无论如何经过 $l_i \rightarrow r_i$ 的操作后 $p$ 都会出现在第 $k$ 个杯子里。因为我们是从 $l_i$ 操作开始的所以 $p=j$ 。

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;
}