题意

给定一个长度为 $n$ 的排列 $p$（下标从 $1$ 开始）。
定义一次“霸凌交换”如下：

$1$. 找到最大的元素 $p_i$ 使得 $p_i \ne i$（即最右边的不在正确位置的元素），记其下标为 $i$。 $2$. 找到最小的元素 $p_j$ 满足 $j > i$（即在 $i$ 右边的最小元素），记其下标为 $j$。 $3$. 交换 $p_i$ 和 $p_j$。

重复执行直到排列变为 $[1,2,\dots,n]$。记 $f(p)$ 为所需的交换次数。
初始时若已是恒等排列，则 $f(p)=0$。

现在有 $q$ 次更新，每次交换 $p_x$ 和 $p_y$（$x<y$），每次更新后输出新的 $f(p)$。
更新是持久化的，即每次交换会改变排列。

---

关键结论

经过分析，霸凌交换的过程等价于：

• 每次操作会将当前最右边的错位元素（$p_i \ne i$ 中最大的 $p_i$）放到它正确的位置，同时把右边最小的元素移到左边。
• 最终，$f(p)$ 可以分解为两部分：$$f(p) = \sum_{i: p_i > i} (p_i - i) + \sum_{i: p_i < i} 1 $$即：
  • 所有 $p_i > i$ 的元素需要向右移动 $p_i - i$ 步
  • 所有 $p_i < i$ 的元素每个贡献 $1$

因此，我们只需要维护这两个部分的和。

---

数据结构

设：

• $ans = \sum_{p_i > i} (p_i - i)$
• $cnt = \#\{i \mid p_i < i\}$

则 $f(p) = ans + cnt$。

当交换 $p_x$ 和 $p_y$（$x<y$）时，只有位置 $x$ 和 $y$ 的贡献会改变。
我们可以用树状数组（BIT）来维护哪些位置满足 $p_i < i$（即这些位置在 BIT 中为 $1$，其余为 $0$），从而 $cnt = \text{BIT.sum}(n)$。

同时，$ans$ 用一个变量直接维护。

---

更新操作

设交换前：

• $a = p_x$，$b = p_y$

步骤 $1$：减去旧贡献

对于位置 $x$：

• 若 $a > x$：$ans$ 减去 $a - x$
• 若 $a < x$：BIT 在 $x$ 处减 $1$

对于位置 $y$：

• 若 $b > y$：$ans$ 减去 $b - y$
• 若 $b < y$：BIT 在 $y$ 处减 $1$

步骤 $2$：交换值

swap(p[x], p[y]);
swap(pos[a], pos[b]);

步骤 $3$：加上新贡献

现在新的 $p_x = b$，$p_y = a$。

对于位置 $x$：

• 若 $b > x$：$ans$ 加上 $b - x$
• 若 $b < x$：BIT 在 $x$ 处加 $1$

对于位置 $y$：

• 若 $a > y$：$ans$ 加上 $a - y$
• 若 $a < y$：BIT 在 $y$ 处加 $1$

步骤 $4$：输出答案

$f(p) = ans + \text{BIT.sum}(n)$

---

复杂度

• 预处理 $O(n)$
• 每次更新 $O(\log n)$（BIT 操作）
• 总复杂度 $O((n+q) \log n)$，可过 $n=5\times10^5$，$q=5\times10^4$

---

完整代码

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

const int N = 5e5 + 5;

int n, q;
int p[N], pos[N];
ll ans = 0;

struct BIT {
    int tree[N];
    void add(int i, int x) {
        for (; i <= n; i += i & -i) tree[i] += x;
    }
    int sum(int i) {
        int s = 0;
        for (; i; i -= i & -i) s += tree[i];
        return s;
    }
    int range(int l, int r) {
        return sum(r) - sum(l - 1);
    }
} bit;

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        pos[p[i]] = i;
        if (p[i] > i) ans += p[i] - i;
        else if (p[i] < i) bit.add(i, 1);
    }

    auto update = [&](int x, int y) {
        // 交换 p[x] 和 p[y]
        int a = p[x], b = p[y];
        // 更新答案
        // 先减去旧贡献
        if (a > x) ans -= a - x;
        else if (a < x) bit.add(x, -1);
        if (b > y) ans -= b - y;
        else if (b < y) bit.add(y, -1);

        swap(p[x], p[y]);
        swap(pos[a], pos[b]);

        // 加上新贡献
        if (a > y) ans += a - y;
        else if (a < y) bit.add(y, 1);
        if (b > x) ans += b - x;
        else if (b < x) bit.add(x, 1);
    };

    while (q--) {
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        update(x, y);
        cout << ans + bit.sum(n) << "\n";
    }

    return 0;
}

---

示例验证

输入：

8 5
6 2 1 5 3 4 7 8
1 8
2 3
4 7
7 8
3 6

输出：

5
6
9
8
7

与题目样例一致。

---

总结

• 将 $f(p)$ 转化为可维护的形式：$f(p) = \sum_{p_i > i} (p_i - i) + \#\{i \mid p_i < i\}$
• 用变量 $ans$ 维护第一部分，用 BIT 维护第二部分
• 每次交换只影响两个位置，$O(\log n)$ 更新