题意回顾

我们需要构造一个长度为 $n$ 的序列 $a[1 \dots n]$，满足 $m$ 个条件：

• 第 $i$ 个条件：$\min\{a_{L_i}, a_{L_i+1}, \dots, a_{R_i}\} = V_i$

在满足所有条件的前提下，最小化冒泡排序的交换次数（即逆序对数）。

数据范围：$T \leq 1000$，$\sum n, \sum m \leq 10^6$。

---

关键转化

1. 冒泡排序交换次数 = 逆序对数

这是经典结论：冒泡排序的交换次数等于序列的逆序对数。

因此问题转化为：在满足区间最小值限制下，构造逆序对数最小的序列。

---

2. 区间最小值条件的分析

条件 $\min\{a_{L_i}, \dots, a_{R_i}\} = V_i$ 意味着：

1. 区间内至少有一个位置等于 $V_i$
2. 区间内所有位置的值 $\geq V_i$

---

算法思路

阶段 1：可行性检查与预处理

步骤 1.1：计算每个位置的最小值下界

对于每个位置 $i$，它必须满足： [ minVal[i] = \max{V_j \mid L_j \leq i \leq R_j} ] 即所有覆盖位置 $i$ 的区间中 $V_j$ 的最大值。

这可以用差分+前缀最大值或线段树区间赋值实现。

步骤 1.2：检查区间最小值条件

对于每个条件 $[L_i, R_i, V_i]$，检查区间 $[L_i, R_i]$ 中是否存在至少一个位置 $j$ 满足： [ minVal[j] = V_i ] 如果不存在，则无解，输出 $-1$。

---

阶段 2：贪心构造序列

为了最小化逆序对，我们希望序列尽可能单调不降。

从左到右构造序列：

• 维护当前值 $cur$
• 对于位置 $i$：
  • 如果 $minVal[i] > cur$，则 $a[i] = minVal[i]$，$cur = minVal[i]$
  • 否则 $a[i] = cur$（保持不降）

这样构造的序列满足：

1. 所有位置值 $\geq minVal[i]$（满足条件2）
2. 序列单调不降（逆序对数为0，如果可行的话）

---

阶段 3：处理必须等于 $V_i$ 的位置

问题：上述构造可能不满足"区间内至少有一个位置等于 $V_i$"。

解决方案：对于每个区间 $[L_i, R_i, V_i]$，我们需要确保区间内至少有一个位置的值恰好等于 $V_i$。

算法：

1. 按 $V_i$ 从大到小处理所有区间

2. 对于当前区间 $[L, R, V]$：

   • 在 $[L, R]$ 中找到第一个满足 $minVal[j] = V$ 且尚未被固定为某个值的位置 $j$
   • 将 $a[j]$ 固定为 $V$
   • 如果找不到这样的位置，则无解

3. 对于其他位置，使用阶段2的贪心方法填充

---

阶段 4：计算逆序对

在构造出序列后，用树状数组或归并排序计算逆序对数。

---

正确性证明

贪心策略的最优性：

• 逆序对数最小化要求序列尽可能接近单调不降
• 我们的构造在满足约束的前提下，让序列尽可能不降
• 可以证明这是最优的

---

复杂度分析

• 预处理：$O(n + m)$（差分）
• 贪心构造：$O(n \log m)$（需要快速查询区间）
• 逆序对计算：$O(n \log n)$
• 总复杂度：$O((n+m) \log n)$，可接受

---

代码实现

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

typedef long long ll;
const int MAXN = 1e6 + 5;

struct Condition {
    int l, r, v;
    bool operator<(const Condition& other) const {
        return v > other.v;  // 按v从大到小排序
    }
};

int n, m;
int minVal[MAXN];  // 每个位置的最小值下界
int a[MAXN];       // 构造的序列
bool fixedPos[MAXN]; // 该位置是否已被固定

// 树状数组计算逆序对
struct Fenwick {
    int tree[MAXN];
    void clear() { memset(tree, 0, sizeof(tree)); }
    void update(int x, int v) {
        for (; x <= n; x += x & -x) tree[x] += v;
    }
    int query(int x) {
        int res = 0;
        for (; x; x -= x & -x) res += tree[x];
        return res;
    }
} bit;

// 计算逆序对数
ll countInversions() {
    bit.clear();
    ll res = 0;
    for (int i = n; i >= 1; i--) {
        res += bit.query(a[i] - 1);
        bit.update(a[i], 1);
    }
    return res;
}

void solve() {
    cin >> n >> m;
    
    // 初始化
    for (int i = 1; i <= n; i++) {
        minVal[i] = 0;
        fixedPos[i] = false;
    }
    
    vector<Condition> conds(m);
    vector<vector<int>> add(n + 2), del(n + 2);
    
    // 读入条件并建立差分
    for (int i = 0; i < m; i++) {
        cin >> conds[i].l >> conds[i].r >> conds[i].v;
        add[conds[i].l].push_back(conds[i].v);
        del[conds[i].r + 1].push_back(conds[i].v);
    }
    
    // 计算minVal[i]
    multiset<int> current;
    for (int i = 1; i <= n; i++) {
        for (int v : add[i]) current.insert(v);
        for (int v : del[i]) current.erase(current.find(v));
        if (!current.empty()) {
            minVal[i] = *current.rbegin();  // 最大值
        }
    }
    
    // 按v从大到小处理条件
    sort(conds.begin(), conds.end());
    
    // 检查每个区间是否有位置满足minVal[j] = V_i
    for (auto& cond : conds) {
        int L = cond.l, R = cond.r, V = cond.v;
        bool found = false;
        for (int j = L; j <= R; j++) {
            if (minVal[j] == V && !fixedPos[j]) {
                a[j] = V;
                fixedPos[j] = true;
                found = true;
                break;
            }
        }
        if (!found) {
            cout << -1 << "\n";
            return;
        }
    }
    
    // 贪心填充剩余位置
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        if (fixedPos[i]) {
            cur = a[i];
        } else {
            if (minVal[i] > cur) {
                a[i] = minVal[i];
                cur = minVal[i];
            } else {
                a[i] = cur;
            }
        }
    }
    
    // 最终检查所有条件是否满足
    for (auto& cond : conds) {
        int minV = a[cond.l];
        for (int j = cond.l + 1; j <= cond.r; j++) {
            minV = min(minV, a[j]);
        }
        if (minV != cond.v) {
            cout << -1 << "\n";
            return;
        }
    }
    
    // 计算逆序对
    cout << countInversions() << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

---

总结

本题的关键在于：

1. 问题转化：冒泡排序交换次数 = 逆序对数
2. 贪心构造：在满足约束下让序列尽可能单调不降
3. 处理区间最小值：确保每个区间有恰好等于 $V_i$ 的位置
4. 高效实现：使用差分、线段树等数据结构