问题本质

这是一个动态维护冒泡排序扫描趟数的问题。对于长度为 $N$ 的序列，有 $Q$ 次单点修改，每次修改后需要快速求出当前序列的冒泡排序扫描趟数。

关键结论

经过分析，冒泡排序的扫描趟数等于：

更具体地说，对于位置 $i$，定义：

那么冒泡排序的扫描趟数为 $\max f(i)$。

核心思路

1.问题转化

将问题转化为：维护每个位置 $i$ 的 $f(i)$ 值，并在修改后快速求出全局最大值。

2.数据结构设计

使用权值线段树，以下标为权值（离散化后），维护：

• cnt：区间内存在的元素个数

• mx：区间内 $i-1$ 的最大值（即原始位置减一）

• res：区间内 $f(i)$ 的最大值

3.关键合并操作

线段树合并时：

void penup(int x) {
    tr[x].cnt = tr[ls(x)].cnt + tr[rs(x)].cnt;
    tr[x].mx = max(tr[ls(x)].mx, tr[rs(x)].mx);
    tr[x].res = max(tr[ls(x)].res, tr[rs(x)].res - tr[ls(x)].cnt);
}

这里 tr[rs(x)].res - tr[ls(x)].cnt 表示右子树中某个元素的 $f(i)$ 值，因为左子树的所有元素都小于右子树，所以左子树的元素个数就是右子树元素前面比它大的数的个数。

算法步骤

1.预处理阶段 离散化：将所有初始值和修改值一起离散化，注意要保留下标信息避免重复

for (int i = 1; i <= n; i++)
    p.push_back({a[i], i});
for (int i = 1; i <= T; i++)
    p.push_back({val[i], pos[i]});
stable_sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());

2.建树初始化：

build(1, 1, p.size());
for (int i = 1; i <= n; i++)
    update(1, 1, p.size(), getid({a[i], i}), i - 1);

查询处理 对于每次修改：

删除旧值：update(..., getid({a[pos[i]], pos[i]}), -INF)

更新数组：a[pos[i]] = val[i]

插入新值：update(..., getid({val[i], pos[i]}), pos[i] - 1)

输出答案：tr[1].res 就是全局的 $\max f(i)$

复杂度分析

离散化：$O((N+Q)\log(N+Q))$

建树：$O(N+Q)$

每次修改：$O(\log(N+Q))$

总复杂度：$O((N+Q)\log(N+Q))$，可以处理 $5\times 10^5$ 的数据规模

总结

本题通过深入分析冒泡排序的性质，将扫描趟数转化为每个位置前面比它大的元素个数的函数，进而使用权值线段树动态维护这一信息。算法的核心在于：

问题转化：发现冒泡排序趟数与逆序对的分布关系

数据结构：设计能够维护 $f(i)$ 函数的线段树

合并策略：巧妙的区间合并方式，利用左右子树的偏序关系

离散化处理：处理大值域情况，保证复杂度

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <vector>
#include <map>
#define N 1000005
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lson ls(x),l,mid
#define rson rs(x),mid + 1,r
using namespace std;
int n, T, a[N], cnt, cnt2, pos[N], val[N];
const int INF = 1e9;
vector<pair<int, int>> p;
int getid(pair<int, int> x) {
    return lower_bound(p.begin(), p.end(), x) - p.begin() + 1;
}
struct seg {
    int cnt, mx, res;
} tr[N << 2];
void penup(int x) {
    tr[x].cnt = tr[ls(x)].cnt + tr[rs(x)].cnt;
    tr[x].mx = max(tr[ls(x)].mx, tr[rs(x)].mx);
    tr[x].res = max(tr[ls(x)].res, tr[rs(x)].res - tr[ls(x)].cnt);
}
void build(int x, int l, int r) {
    tr[x] = {0, -INF, -INF};

    if (l == r)
        return;

    int mid = l + r >> 1;
    build(lson), build(rson);
}
void update(int x, int l, int r, int pos, int val) {
    if (l == r)
        return tr[x] = {val != -INF, val, val}, void();
    int mid = l + r >> 1;

    if (mid >= pos)
        update(lson, pos, val);
    else
        update(rson, pos, val);

    penup(x);
}
signed main() {
    //  freopen("trunk.in","r",stdin),freopen("trunk.out","w",stdout);
    cin >> n >> T;

    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    for (int i = 1; i <= n; i ++)
        p.push_back({a[i], i});

    for (int i = 1; i <= T; i ++)
        scanf("%d%d", &pos[i], &val[i]), pos[i] ++, p.push_back({val[i], pos[i]});
    stable_sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    build(1, 1, p.size());

    //  cout << p.size() << endl;
    for (int i = 1; i <= n; i ++)
        update(1, 1, p.size(), getid({a[i], i}), i - 1);

    //  cout << getid({a[i],i});
    //  for (int i = 1;i <= p.size();i ++) cout << tr[i].res << endl;
    for (int i = 1; i <= T; i ++) {
        update(1, 1, p.size(), getid({a[pos[i]], pos[i]}), -INF);
        a[pos[i]] = val[i];
        update(1, 1, p.size(), getid({val[i], pos[i]}), pos[i] - 1);
        printf("%d\n", tr[1].res);
    }

    return 0;
}