题解

问题转化

我们有两个排列 $p$ 和 $s$，物品 $i$ 可以到达物品 $j$ 当且仅当存在一个交换序列，每次使用第一个商人（需要 $p_{\text{当前}} > p_{\text{目标}}$）或第二个商人（需要 $s_{\text{当前}} > s_{\text{目标}}$）。

关键结论：由于两个商人的交换规则都是严格递减，且可以交替使用，物品 $i$ 能到达物品 $j$ 当且仅当：

$$p_i > p_j \quad \text{且} \quad s_i > s_j$$

即两个坐标都严格大于。

答案公式

设 $\text{dom}(i)$ 表示满足 $p_j < p_i$ 且 $s_j < s_i$ 的物品 $j$ 的数量（$j \neq i$）。

那么所有满足 $p_i > p_j$ 且 $s_i > s_j$ 的有序对 $(i,j)$（$i \neq j$）的数量就是：

$$\text{inv} = \sum_{i=1}^{n} \text{dom}(i)$$

加上自环 $(i,i)$，最终答案：

$$\text{ans} = n + \text{inv}$$

动态维护

每次交换 $p$ 或 $s$ 中的两个位置时，只有这两个物品的坐标发生变化。因此，只有这两个物品的 $\text{dom}$ 值会改变，且它们之间的相互贡献也会改变。

设当前交换的物品是 $a$ 和 $b$：

• 记 $\text{ab} = [p_a > p_b \text{ 且 } s_a > s_b]$
• 记 $\text{ba} = [p_b > p_a \text{ 且 } s_b > s_a]$

更新公式：

$$\text{inv}_{\text{new}} = \text{inv}_{\text{old}} - (\text{dom}(a) + \text{dom}(b) + \text{ab} + \text{ba})_{\text{old}} + (\text{dom}(a) + \text{dom}(b) + \text{ab} + \text{ba})_{\text{new}} $$

实现细节

初始化：按 $p$ 升序排序，用 Fenwick 树维护 $s$ 值，计算每个物品的 $\text{dom}(i)$。

查询处理：

1. 减去旧的贡献
2. 交换 $p$ 或 $s$
3. 重新计算 $a$ 和 $b$ 的 $\text{dom}$ 值（代码中用 $O(n)$ 的 calc_dom，实际可用 BIT 优化到 $O(\log n)$）
4. 加上新的贡献
5. 输出 $n + \text{inv}$

完整代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n_) : n(n_), bit(n_ + 1, 0) {}
    void add(int idx, int delta) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
    }
    int sum(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
    int range_sum(int l, int r) {
        if (l > r) return 0;
        return sum(r) - sum(l - 1);
    }
};

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

    int t;
    cin >> t;
    while (t--) {
        int n, q;
        cin >> n >> q;
        vector<int> p(n), s(n);
        for (int i = 0; i < n; ++i) cin >> p[i];
        for (int i = 0; i < n; ++i) cin >> s[i];

        // 离散化 s
        vector<int> ss = s;
        sort(ss.begin(), ss.end());
        auto get_s_idx = [&](int val) {
            return lower_bound(ss.begin(), ss.end(), val) - ss.begin() + 1;
        };

        // 按 p 升序处理，BIT 按 s 下标维护
        vector<tuple<int, int, int>> items;
        for (int i = 0; i < n; ++i) {
            items.emplace_back(p[i], s[i], i);
        }
        sort(items.begin(), items.end());

        Fenwick bit(n);
        vector<int> dom(n, 0);
        for (auto [pi, si, id] : items) {
            int idx = get_s_idx(si);
            dom[id] = bit.sum(idx - 1);
            bit.add(idx, 1);
        }

        ll inv = 0;
        for (int i = 0; i < n; ++i) inv += dom[i];

        vector<int> cur_p = p, cur_s = s;

        auto calc_dom = [&](int id) {
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if (j != id && cur_p[j] < cur_p[id] && cur_s[j] < cur_s[id]) ++cnt;
            }
            return cnt;
        };

        while (q--) {
            int tp, a, b;
            cin >> tp >> a >> b;
            --a; --b;

            if (tp == 1) {
                int old_dom_a = dom[a], old_dom_b = dom[b];
                int ab = (cur_p[a] > cur_p[b] && cur_s[a] > cur_s[b]) ? 1 : 0;
                int ba = (cur_p[b] > cur_p[a] && cur_s[b] > cur_s[a]) ? 1 : 0;

                inv -= (old_dom_a + old_dom_b + ab + ba);

                swap(cur_p[a], cur_p[b]);

                dom[a] = calc_dom(a);
                dom[b] = calc_dom(b);
                ab = (cur_p[a] > cur_p[b] && cur_s[a] > cur_s[b]) ? 1 : 0;
                ba = (cur_p[b] > cur_p[a] && cur_s[b] > cur_s[a]) ? 1 : 0;

                inv += (dom[a] + dom[b] + ab + ba);
            } else {
                int old_dom_a = dom[a], old_dom_b = dom[b];
                int ab = (cur_p[a] > cur_p[b] && cur_s[a] > cur_s[b]) ? 1 : 0;
                int ba = (cur_p[b] > cur_p[a] && cur_s[b] > cur_s[a]) ? 1 : 0;

                inv -= (old_dom_a + old_dom_b + ab + ba);

                swap(cur_s[a], cur_s[b]);

                dom[a] = calc_dom(a);
                dom[b] = calc_dom(b);
                ab = (cur_p[a] > cur_p[b] && cur_s[a] > cur_s[b]) ? 1 : 0;
                ba = (cur_p[b] > cur_p[a] && cur_s[b] > cur_s[a]) ? 1 : 0;

                inv += (dom[a] + dom[b] + ab + ba);
            }

            cout << n + inv << '\n';
        }
    }
    return 0;
}

时间复杂度

朴素实现 $O(nq)$，但每个物品的 $\text{dom}$ 可用 BIT 优化到 $O(\log n)$，总复杂度 $O((n+q)\log n)$。