题意

给定 $n$ 个区间 $[l_i, r_i]$，满足 $l_i < r_i$ 且所有 $2n$ 个端点互不相同。
第 $i$ 个区间的单位长度权重为 $c_i$，总权重为 $c_i \cdot (r_i - l_i)$。
你可以任意重新排列 $l$ 数组、$r$ 数组和 $c$ 数组，但必须保证重新排列后每个区间仍然满足 $l_i < r_i$。
目标：最小化所有区间权重总和。

---

关键结论

最优构造：

1. 将所有 $2n$ 个端点混合排序，遇到左端点视为 (，右端点视为 )，得到一个合法括号序列。
2. 用栈进行括号匹配：每个右括号与它之前最近且未匹配的左括号配对，得到 $n$ 个区间。
3. 将这些区间的长度升序排序，将权重 $c$ 降序排序，对应相乘求和即得最小总权重。

---

正确性证明

1. 括号序列的合法性

将 $l_1,\dots,l_n,r_1,\dots,r_n$ 混合后升序排列。因为每个 $l_i$ 都对应一个大于它的 $r_i$，所以在任意前缀中，左括号（$l$）的个数不少于右括号（$r$）的个数。因此括号序列是正则括号序列，栈匹配一定成功，且匹配出的区间两两不交叉（完全嵌套或相离）。

2. 最优配对证明

假设存在另一种配对方式，使得某两个区间 $[l_i,r_i]$ 和 $[l_j,r_j]$ 满足交叉关系 $l_i < l_j < r_i < r_j$（即非嵌套）。
设这两个区间对应的单位权重分别为 $c_i$ 和 $c_j$，且不妨设 $c_i \le c_j$（否则交换权重，因为权重可任意重排）。
交换它们的右端点，得到新区间 $[l_i, r_j]$ 和 $[l_j, r_i]$。计算成本变化：

$$\begin{aligned} \Delta &= \big[c_i(r_j-l_i) + c_j(r_i-l_j)\big] - \big[c_i(r_i-l_i) + c_j(r_j-l_j)\big] \\ &= (c_i - c_j)(r_j - r_i) \le 0. \end{aligned} $$

因此交换不增加总成本。重复这样的交换，可以消除所有交叉结构，最终得到完全嵌套的区间集合——这正是括号匹配的结果。由于每次交换成本不增，括号匹配给出的区间集合一定是最优的。

3. 权重分配

得到区间长度数组 $\text{len}_1,\dots,\text{len}_n$ 后，我们需要分配权重 $c_i$ 以最小化 $\sum \text{len}_i \cdot c_{\sigma(i)}$。
由排序不等式：两个序列同序时乘积和最大，逆序时乘积和最小。因此将 $\text{len}$ 升序排列，$c$ 降序排列，对应相乘即得最小和。

---

算法步骤

1. 读入 $n$ 以及数组 $l[1..n], r[1..n], c[1..n]$。
2. 创建点集 $\text{points}$：每个左端点标记为 $0$，右端点标记为 $1$。按值排序。
3. 初始化一个栈 $\text{st}$，遍历排序后的点：
   • 若遇到左端点（type $=0$），将其值压入栈。
   • 若遇到右端点（type $=1$），弹出栈顶左端点，计算区间长度 $= \text{val} - \text{left}$，存入数组 $\text{lens}$。
4. 将 $\text{lens}$ 升序排序，将 $c$ 降序排序。
5. 计算 $\displaystyle \text{ans} = \sum_{i=1}^{n} \text{lens}[i] \cdot c[i]$，输出 $\text{ans}$。

---

复杂度分析

• 排序端点：$O(n \log n)$
• 栈扫描：$O(n)$
• 排序长度和权重：$O(n \log n)$
• 总时间复杂度 $O(n \log n)$，空间 $O(n)$。所有测试用例 $n$ 总和 $\le 10^5$，可在 $1$ 秒内完成。

---

参考代码（C++）

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

void solve() {
    int n;
    cin >> n;
    vector<int> l(n), r(n), c(n);
    for (int i = 0; i < n; ++i) cin >> l[i];
    for (int i = 0; i < n; ++i) cin >> r[i];
    for (int i = 0; i < n; ++i) cin >> c[i];

    vector<pair<int, int>> points; // (value, type) type: 0=left, 1=right
    for (int x : l) points.emplace_back(x, 0);
    for (int x : r) points.emplace_back(x, 1);
    sort(points.begin(), points.end());

    vector<int> lens;
    stack<int> st;
    for (auto [val, type] : points) {
        if (type == 0) {
            st.push(val);
        } else {
            int left = st.top(); st.pop();
            lens.push_back(val - left);
        }
    }

    sort(lens.begin(), lens.end());
    sort(c.begin(), c.end(), greater<int>());

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += 1LL * lens[i] * c[i];
    }
    cout << ans << '\n';
}

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

---

样例验证

样例输入

2
2
8 3
12 23
100 100
4
20 1 2 5
30 4 3 10
2 3 2 3

样例输出

2400
42

与题目要求一致。

---

总结

本题核心在于将区间配对问题转化为括号匹配，再利用排序不等式分配权重。理解“交叉交换不增成本”的贪心思想后，实现非常简单。注意使用 long long 避免乘积溢出。