题目理解

我们有一个长度为 $n$ 的序列，每本书有两个属性：

• 当前位置 $wz$（实际摆放位置）
• 页数 $ys$（权重）

厌烦度定义：对于所有逆序对 $(i, j)$（即 $i < j$ 但 $wz_i > wz_j$），其贡献为 $ys_i + ys_j$。总厌烦度是所有逆序对的贡献之和。

操作：每次交换两本书的位置，需要动态维护当前的总厌烦度。

---

核心思路

1. 问题转化

设当前序列为 $p_1, p_2, \dots, p_n$，其中 $p_i$ 表示位置 $i$ 上的书。

厌烦度可以表示为：

$$\text{ans} = \sum_{i=1}^n \sum_{j=i+1}^n [wz_{p_i} > wz_{p_j}] \cdot (ys_{p_i} + ys_{p_j}) $$

这可以拆分为：

$$\text{ans} = \sum_{i=1}^n \left( ys_i \cdot (\text{位置在 i 后面且 wz 值更小的书的数量}) + \sum_{j: j>i, wz_j < wz_i} ys_j \right) $$

---

2. 数据结构设计

使用 树状数组套权值线段树 来维护二维信息：

• 第一维：序列位置（树状数组维护）
• 第二维：$wz$ 值（线段树维护）

每个线段树节点维护：

• z0：书本数量
• z1：书本页数之和

---

3. 关键操作

查询函数 ans(x, w, val)

• 查询序列前 $x$ 个位置中，$wz$ 值在 $[1, w]$ 范围内的信息
• 返回：$val \times \text{数量} + \text{页数和}$

计算逆序对贡献

对于位置 $i$，其作为逆序对左端点的贡献为：

$$\text{ans}(i, n, ys_i) - \text{ans}(i, wz_i, ys_i) $$

• 第一部分：前 $i$ 个位置中，$wz$ 值在 $[1, n]$ 的所有书对 $i$ 的贡献
• 第二部分：前 $i$ 个位置中，$wz$ 值在 $[1, wz_i]$ 的所有书对 $i$ 的贡献
• 差值就是 $wz$ 值在 $(wz_i, n]$ 的书本（即逆序对）的贡献

---

4. 交换操作处理

交换位置 $x$ 和 $y$ 的书时：

1. 删除原贡献：

   • 分别移除位置 $x$ 和 $y$ 上的书对总厌烦度的贡献
   • 包括它们作为左端点和右端点的贡献

2. 执行交换：swap(sj[x], sj[y])

3. 添加新贡献：

   • 分别添加位置 $x$ 和 $y$ 上的新书对总厌烦度的贡献
   • 同样包括作为左端点和右端点的贡献

---

代码解析

#include <bits/stdc++.h>
#define low(x) ((x)&(-x))
using namespace std;
const unsigned long long mod = 1000000007;
int n, m;
struct SJ {
    int wz, ys;  // 位置和页数
} sj[50005];

struct MMT {
    int z0, z1;    // 数量，页数和
    int ls, rs;    // 左右儿子
} mmt[15000000];

long long an;      // 总厌烦度
int tot, root[50005];  // 线段树根节点

// 线段树更新：在位置x处添加/删除一本书
void j(int w, int l, int r, int x, int ys, int z) {
    if (l == r) {
        mmt[w].z0 += z;
        mmt[w].z1 = (mmt[w].z1 + ys * z + mod) % mod;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        if (mmt[w].ls == 0) tot++, mmt[w].ls = tot;
        j(mmt[w].ls, l, mid, x, ys, z);
    } else {
        if (mmt[w].rs == 0) tot++, mmt[w].rs = tot;
        j(mmt[w].rs, mid + 1, r, x, ys, z);
    }
    mmt[w].z0 += z;
    mmt[w].z1 = (mmt[w].z1 + ys * z + mod) % mod;
}

// 树状数组更新：在序列位置x处更新
void add(unsigned short x, unsigned short w, int ys, int z) {
    for (int i = x; i <= n; i += low(i))
        j(root[i], 1, n, w, ys, z);
}

// 线段树查询：返回 val*数量 + 页数和
long long h(int w, int l, int r, int x, int y, long long val) {
    if (x <= l && r <= y)
        return (val * mmt[w].z0 % mod + mmt[w].z1) % mod;
    int mid = (l + r) >> 1;
    long long zh = 0;
    if (x <= mid && mmt[w].ls != 0)
        zh = (zh + h(mmt[w].ls, l, mid, x, y, val)) % mod;
    if (y > mid && mmt[w].rs != 0)
        zh = (zh + h(mmt[w].rs, mid + 1, r, x, y, val)) % mod;
    return zh;
}

// 树状数组查询：前x个位置中，wz值在[1,w]范围内的信息
long long ans(unsigned short x, unsigned short w, long long val) {
    long long res = 0;
    for (int i = x; i; i -= low(i))
        res = (res + h(root[i], 1, n, 1, w, val)) % mod;
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        cin >> sj[i].wz >> sj[i].ys;
        root[i] = i, tot++;
    }
    
    // 初始构建
    for (int i = 1; i <= n; i++) {
        add(i, sj[i].wz, sj[i].ys, 1);
        an = (an + ans(i, n, sj[i].ys) - ans(i, sj[i].wz, sj[i].ys) + mod) % mod;
    }
    
    // 处理交换操作
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        
        // 删除x和y的旧贡献
        an = (an - (ans(x, n, sj[x].ys) - ans(x, sj[x].wz, sj[x].ys) + mod) % mod + mod) % mod;
        an = (an - (ans(n, sj[x].wz-1, sj[x].ys) - ans(x, sj[x].wz-1, sj[x].ys) + mod) % mod + mod) % mod;
        add(x, sj[x].wz, sj[x].ys, -1);
        
        an = (an - (ans(y, n, sj[y].ys) - ans(y, sj[y].wz, sj[y].ys) + mod) % mod + mod) % mod;
        an = (an - (ans(n, sj[y].wz-1, sj[y].ys) - ans(y, sj[y].wz-1, sj[y].ys) + mod) % mod + mod) % mod;
        add(y, sj[y].wz, sj[y].ys, -1);
        
        // 交换并添加新贡献
        swap(sj[x], sj[y]);
        
        add(x, sj[x].wz, sj[x].ys, 1);
        an = (an + ans(x, n, sj[x].ys) - ans(x, sj[x].wz, sj[x].ys) + mod) % mod;
        an = (an + ans(n, sj[x].wz-1, sj[x].ys) - ans(x, sj[x].wz-1, sj[x].ys) + mod) % mod;
        
        add(y, sj[y].wz, sj[y].ys, 1);
        an = (an + ans(y, n, sj[y].ys) - ans(y, sj[y].wz, sj[y].ys) + mod) % mod;
        an = (an + ans(n, sj[y].wz-1, sj[y].ys) - ans(y, sj[y].wz-1, sj[y].ys) + mod) % mod;
        
        cout << an << '\n';
    }
    return 0;
}

---

复杂度分析

• 空间复杂度：$O(n \log n)$，动态开点线段树
• 时间复杂度：每次更新和查询 $O(\log^2 n)$，总复杂度 $O((n + m) \log^2 n)$

---

总结

这道题的核心在于：

1. 将厌烦度计算转化为带权逆序对问题
2. 使用树状数组套线段树维护二维信息
3. 动态维护交换操作对逆序对的影响
4. 通过拆解贡献来分别处理每个位置的贡献