题目大意：

n ( ≤ 2 e 5 ) n(\le 2e5) n(≤2e5)个数轴上的点， m ( ≤ 2 e 5 ) m(\le 2e5) m(≤2e5)个数轴上的线段。每一次可以移动任意一个点移动单位一的距离

最少操作多少次可以使的每个线段至少被一个点访问过

解题思路：

• 对于本身覆盖了点的线段可以删除掉

• 对于大的线段覆盖了小的线段，大的线段可以删除掉，因为要遍历到小线段，则必然会经过大线段，所以可以删除

• 对于两个点之间的线段，显然是由这两点来访问是最优的

• 设 d p [ i ] [ k ] dp[i][k] dp[i][k]为第 i i i个点访问右边 k k k个线段的最小值，有 d p dp dp方程：
  d p [ i ] [ k ] = m i n ( d p [ i − 1 ] [ j ] + 2 ∗ m i n ( a [ i ] − r i − 1 [ j + 1 ] , l i [ k ] − a [ i ] ) + m a x ( a [ i ] − r i − 1 [ j + 1 ] , l i [ k ] − a [ i ] ) ) 因 为 要 对 于 第 i 个 点 ， 如 果 要 访 问 两 边 的 线 段 ， 必 然 会 存 在 先 访 问 右 边 还 是 先 访 问 左 边 的 问 题 ， 而 显 然 是 先 访 问 小 的 距 离 先 通 过 以 上 d p 方 程 ， 时 间 复 杂 度 似 乎 是 O ( n 2 ) 的 但 是 可 以 发 现 ， 如 果 a [ i ] − r i − 1 [ j + 1 ] 以 及 l i [ k ] − a [ i ] 都 随 j ， k 单 调 的 所 以 可 以 用 双 指 针 以 及 m u l t s e t 优 化 且 d p 方 程 可 以 变 形 为 如 下 方 程 ： d p [ i ] [ k ] = m i n ( d p [ i − 1 ] [ j ] + l i [ k ] − r i − 1 [ j + 1 ] + m i n ( a [ i ] − r i − 1 [ j + 1 ] , l i [ k ] − a [ i ] ) ) dp[i][k]=min(dp[i - 1][j] + 2 * min(a[i] - r_{i-1}[j + 1], l_i[k]-a[i])+max(a[i] - r_{i-1}[j + 1], l_i[k]-a[i])) \\ 因为要对于第i个点，如果要访问两边的线段，必然会存在先访问右边还是先访问左边的问题，而显然是先访问小的距离先 \\ 通过以上dp方程，时间复杂度似乎是O(n^2)的 \\ 但是可以发现，如果a[i]-r_{i-1}[j+1]以及l_i[k]-a[i]都随j，k单调的所以可以用双指针以及multset优化 \\ 且dp方程可以变形为如下方程： \\ dp[i][k]=min(dp[i-1][j]+l_i[k]-r_{i-1}[j+1]+min(a[i] - r_{i-1}[j + 1], l_i[k]-a[i])) dp[i][k]=min(dp[i−1][j]+2∗min(a[i]−ri−1​[j+1],li​[k]−a[i])+max(a[i]−ri−1​[j+1],li​[k]−a[i]))因为要对于第i个点，如果要访问两边的线段，必然会存在先访问右边还是先访问左边的问题，而显然是先访问小的距离先通过以上dp方程，时间复杂度似乎是O(n2)的但是可以发现，如果a[i]−ri−1​[j+1]以及li​[k]−a[i]都随j，k单调的所以可以用双指针以及multset优化且dp方程可以变形为如下方程：dp[i][k]=min(dp[i−1][j]+li​[k]−ri−1​[j+1]+min(a[i]−ri−1​[j+1],li​[k]−a[i]))

• 想的时候想起来觉得挺复杂的，但是写起来只要明了了就还好

AC代码：

#include <bits/stdc++.h>
#define ft first
#define sd second
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) //不能跟puts混用
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 2e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll inf = 2e15 + 7;
int t, n, m, cnts;
ll a[maxn];
pii seg[maxn], tseg[maxn];
vector <int> len[maxn]; //分段,len[i]中的线段全在i-1~i号点范围内
ll dp[2][maxn], lp[maxn], rp[maxn], ln[maxn], rn[maxn];
multiset <ll> s;
void init0() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> seg[i].ft >> seg[i].sd;
    sort (a + 1, a + n + 1);
    sort (seg + 1, seg + m + 1);
    /* 初始化 */
    a[0] = -inf;
    cnts = 0;
    for (int i = 1; i <= max(n, m) + 1; i++) len[i].clear(), dp[0][i] = dp[1][i] = inf;
    dp[0][0] = dp[0][1] = inf;
    
}
void init1() {
    /*这部分先将已经有点在里面的删除掉*/
    int p = 1, i = 1, j;
    a[n + 1] = 1e9 + 10;
    while (i <= m) {
        if (seg[i].ft <= a[p] && a[p] <= seg[i].sd) i++;
        else if (a[p] < seg[i].ft) p++;        
        else tseg[++cnts] = seg[i], i++;
    }
    for (int i = 1; i <= cnts; i++) seg[i] = tseg[i];
    m = cnts;
    /*这部分将那些大的包含小的，大段删除掉，保留小的*/
    cnts = 1;
    for (int i = 2; i <= m; i++) {
    //    seg[cnts].sd = seg[i].sd;
        if (seg[cnts].sd < seg[i].sd) seg[++cnts] = seg[i];        
        else {
            while (seg[cnts].sd >= seg[i].sd && cnts > 0) cnts--;
            seg[++cnts] = seg[i];
        }
    }

    m = cnts;

    /* 分段 */
    for (i = 1, j = 1; i <= n; i++) {
        for (; j <= m; j++) {
            if (seg[j].sd < a[i]) 
                len[i].pb(j);
            else break;
        }
    }
    while (j <= m) len[n + 1].pb(j++);
}
void init2() {
    int p = 0, id;
    ll res = 0;
    if (len[1].empty()) { //前面为空
        dp[1][0] = 0;
        for (int i = 0; i < len[2].size(); i++) dp[1][i + 1] = seg[len[2][i]].ft - a[1];
    }
    else {
        for (int i = 0; i < len[1].size(); i++) {
            p = len[1][i];
            if (res < a[1] - seg[p].sd) id = p, res = a[1] - seg[p].sd;
        }
        len[1].clear();
        len[1].pb(id);  
        for (int i = 0; i < len[2].size(); i++) {
            p = len[2][i];
            if (seg[p].ft - a[1] > a[1] - seg[id].sd) dp[1][i + 1] = 2 * (a[1] - seg[id].sd) + seg[p].ft - a[1];
            else dp[1][i + 1] = 2 * (seg[p].ft - a[1]) + a[1] - seg[id].sd;
        }
        dp[1][0] = a[1] - seg[id].sd;        
    }
    return;

}
void solve() {
    for (int i = 2; i <= n; i++) {
        int p1 = 0, p2 = len[i + 1].size();
        int pre = (i - 1) & 1, now = i & 1;
        int num1 = len[i].size(), num2 = len[i + 1].size();
        /*start:为了方便将点之间线段存到另一个数组里*/
        for (int j = 1; j <= num1; j++) lp[j] = seg[len[i][j - 1]].ft, rp[j] = seg[len[i][j - 1]].sd;
        lp[0] = rp[0] = a[i - 1];
        lp[num1 + 1] = rp[num1 + 1] = a[i];

        for (int j = 1; j <= num2; j++) ln[j] = seg[len[i + 1][j - 1]].ft, rn[j] = seg[len[i + 1][j - 1]].sd;
        ln[0] = rn[0] = a[i];
        ll mmin = inf;
        /*end*/

        /*start:将值存入multiset中*/
        s.clear();
        for (int j = 0; j <= num1; j++) s.insert(dp[pre][j] - 2 * rp[j + 1] + a[i]);
        int test = s.size();
        /*end*/
        while (p1 <= num1 && p2 >= 0) {
            while (ln[p2] - a[i] <= a[i] - rp[p1 + 1] && p1 <= num1) {
                mmin = min(mmin, dp[pre][p1] - rp[p1 + 1]);
                s.erase(s.find(dp[pre][p1] - 2 * rp[p1 + 1] + a[i]));
                p1++;
            }
            if (!s.empty()) dp[now][p2] = min(mmin + ln[p2] - a[i], (*s.begin())) + ln[p2];
            else dp[now][p2] = mmin + 2 * ln[p2] - a[i];
            p2--;
        }
        while (p2 >= 0) dp[now][p2] = mmin + ln[p2] - a[i] + ln[p2], p2--; 
    }
}
int main() {
    cin >> t;
    while (t--) {
        init0(); //输入并进行整个数组的初始化
        init1(); //将某些无用的线段去除掉并进行分段
        init2(); //预处理开头的点
        solve();
        cout << max(dp[n & 1][len[n + 1].size()], 0ll) << endl;
    }
    
    return 0;
}