Cow Checkups

题意

给定两个长度为 N 的数组：

a[i]：当前第 i 头牛的品种；
b[i]：兽医希望第 i 个位置出现的品种。

FJ 必须选择一个区间 [l,r]，把这个区间反转一次。对所有可能的 [l,r]，分别统计反转后有多少个位置满足品种匹配，并把这些数量全部加起来。

思路

先看一个最直接的暴力：枚举所有反转区间，模拟反转后的数组，再统计匹配位置。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:26
 * update_at: 2026-07-11 18:30
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n;
int a[MAXN], b[MAXN], cur[MAXN];

int count_checked_after_reverse(int l, int r) {
    for (int i = 1; i <= n; i++) {
        cur[i] = a[i];
    }

    int x = l;
    int y = r;
    while (x < y) {
        swap(cur[x], cur[y]);
        x++;
        y--;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (cur[i] == b[i]) {
            cnt++;
        }
    }
    return cnt;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }

    long long ans = 0;
    // 枚举所有反转区间，直接模拟反转后的检查数量。
    for (int l = 1; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            ans += count_checked_after_reverse(l, r);
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

这个暴力能准确表达题意，但复杂度是 $O(N^3)$ ，无法通过满分数据。

换一个角度，不枚举反转区间，而是枚举“哪头原来的牛最终被送到哪个目标位置”。

假设原来第 i 个位置的牛会在反转后到达第 j 个位置，并且 a[i] == b[j]，那么这头牛会对答案贡献若干个反转区间。

如果使用 1-index，下标满足 i < j 时，反转区间 [l,r] 要把 i 送到 j，必须满足：

l + r = i + j

并且 [l,r] 要同时包含 i 和 j。可选的 l 的数量为：

\min(i, N-j+1)

所以每一对满足 a[i] == b[j] 且 i < j 的位置，贡献就是：

\min(i, N-j+1)

i > j 的情况完全对称，把 a 和 b 同时反转后再做一次同样的统计即可。

还剩下 $i == j$ 。如果 a[i] == b[i]，有两类反转区间会让这头牛仍然在位置 i：

反转区间完全在 i 左边或完全在 i 右边；
反转区间包含 i，并且 i 是这个区间的中心。

代码里用 0-index 写成：

text

1ways2(i) + ways2(n - 1 - i) + min(i, n - 1 - i) + 1

接下来需要快速统计所有 i < j 的贡献。对每个品种 v 单独处理：

从右往左扫描；
遇到 b[j] == v，记录这个目标位置；
遇到 a[i] == v，就把所有已经记录的、在右侧的 b[j] 对 i 的贡献加起来。

对一个固定的 i，每个右侧的 j 贡献：

\min(i, N-j+1)

把 $x = N-j+1$ 看成右侧距离。扫描从右往左进行时，查询的 i 会越来越小。于是可以维护：

small_sum：当前还能直接贡献 x 的那些右侧位置的 x 之和；
big_count：那些 x > i 的右侧位置数量，它们每个只能贡献 i；
一个栈，保存还在 small_sum 中的 x。

每次查询位置 i 时，把栈顶所有 x > i 的值移到 big_count 中，然后答案增加：

small\_sum + big\_count \times i

这样每个位置只会入栈、出栈一次，所以总复杂度是线性的。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:26
 * update_at: 2026-07-11 18:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005;

int n;
int a[MAXN], b[MAXN];
vector<pair<int, int> > occ[MAXN];

ll ways2(ll x) {
    return x * (x + 1) / 2;
}

ll calc_one_direction() {
    for (int v = 1; v <= n; v++) {
        occ[v].clear();
    }

    for (int i = 0; i < n; i++) {
        occ[b[i]].push_back(make_pair(i, 1)); // 1 表示 b 中的位置
        occ[a[i]].push_back(make_pair(i, 0)); // 0 表示 a 中的位置
    }

    ll res = 0;

    for (int value = 1; value <= n; value++) {
        vector<int> small_stack;
        int big_count = 0;
        ll small_sum = 0;

        // 从右往左处理同一种品种的出现位置。
        for (int k = (int)occ[value].size() - 1; k >= 0; k--) {
            int idx = occ[value][k].first;
            int type = occ[value][k].second;

            if (type == 1) {
                int dist_right = n - idx;
                small_stack.push_back(dist_right);
                small_sum += dist_right;
            } else {
                int left_choices = idx + 1;
                while (!small_stack.empty() && small_stack.back() > left_choices) {
                    small_sum -= small_stack.back();
                    small_stack.pop_back();
                    big_count++;
                }
                res += small_sum + 1LL * big_count * left_choices;
            }
        }
    }

    return res;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    ll ans = 0;

    // i == j 的贡献：反转区间不包含 i，或者包含 i 且 i 仍在中心。
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) {
            ans += ways2(i) + ways2(n - 1 - i) + min(i, n - 1 - i) + 1;
        }
    }

    ans += calc_one_direction();

    reverse(a, a + n);
    reverse(b, b + n);
    ans += calc_one_direction();

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

每个品种的出现位置总共只被处理常数次，两次方向统计也是线性的。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是把“枚举反转区间”改成“枚举原位置和目标位置的匹配贡献”。

先把单个 (i,j) 的贡献公式推出来，再按品种从右往左维护所有右侧目标位置，就能把平方级配对统计优化到线性。

目录

题意

思路

代码

复杂度

总结