OiClass TIGAO P3280 牛牛的猜球游戏题解

思路

首先考虑暴力的做法，直接依题意模拟模拟，时间复杂度是 \(\mathcal{O}(nm)\)，显然不能通过。但是我们可以发现这种修改方式似乎很适合预处理，然后我就想到了使用前缀和的做法。然后每次进行替代，但是经过一段时间的调试，无法通过，果断放弃。

我们考虑时间复杂度稍高的分块做法，我们规定块长为 \(\sqrt{n}\)，然后将 \(n\) 次操作分成 \(\sqrt{n}\) 个块，对于每个块，我们使用暴力的方式预处理每一个快中操作的结果。

然后对于每一次查询，我们先是用暴力的方法跳到一个块的起点，然后一块一块的王后跳，跳到不够一个块的时候就再次使用暴力的方法往后计算答案。这样操作时间复杂度是 \(\mathcal{O}(n + m\sqrt{n})\) 的，跑满只要 \(3 \times 10^7\)，非常可过。事实也证明了这一点，我的程序最满点只要 \(300\, \rm ms\) 就能跑完。但是隔壁 ty_xyz 的代码需要整整 \(1.5\,\rm s\)，不知为何。

当然，由于分块和线段树有很多共性，我们可以使用线段树维护这样的东西，我想不明白，就不讲了，时间复杂度 \(\mathcal{O}(m \log n)\)，也是非常优的（参考 ty_xyz 的做法）。当然如果你是 DP 大佬，也可以 \(O(m + n)\) 做，但是我也不会，可以参考 lovely_akcode 的做法。

代码

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

#define endl '\n'

using namespace std;

int n, m, blksize, blkcnt, blk[100009][20], a[20], b[20];
vector<pair<int, int>> v;

signed main() {
    freopen("ball.in", "rt", stdin);
    freopen("ball.out", "wt", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    blksize = sqrt(n);
    for (int j = 0; j < 10; j++) {
        a[j] = j;
    }
    for (int i = 1, a, b; i <= n; i++) {
        cin >> a >> b;
        v.push_back({a, b});
        swap(::a[a], ::a[b]);
        if (i % blksize == 0) {
            memcpy(blk[blkcnt++], ::a, sizeof(::a));
            for (int j = 0; j < 10; j++) {
                ::a[j] = j;
            }
        }
    }
    for (int i = 1, l, r; i <= m; i++) {
        cin >> l >> r;
        l -= 1; r -= 1;
        for (int j = 0; j < 10; j++) {
            a[j] = j;
        }
        for (; l % blksize != 0 && l <= r; l++) {
            swap(a[v[l].first], a[v[l].second]);
        }
        for (; l + blksize <= r; l += blksize) {
            for (int j = 0; j < 10; j++) {
                b[j] = a[blk[l / blksize][j]];
            }
            memcpy(a, b, sizeof(a));
        }
        for (; l <= r; l++) {
            swap(a[v[l].first], a[v[l].second]);
        }
        for (int j = 0; j < 10; j++) {
            cout << a[j] << " ";
        }
        cout << endl;
    }
}