【题解】CF1566F

先考虑对这些线段进行一些精简。

显然，区间内已经有点的线段可以被扔掉，完整包含了另一条线段的线段也可以被扔掉。两个过程都可以用二分实现。

观察一下整个画面现在长什么样子：大概是一堆线段 - 一堆点 - 一堆线段 - 一堆点这样，并且线段左端点随线段右端点递增而递增。观察一下最优方案应该长什么样子：显然，任意两个点跑过的的位置都不应该存在公共点。

设一个点初始位置为 $x$ ，跑过的位置为 $[l, r]$ 这个区间，那么这个点造成的花费是 $(r - l) + \min(x-l, r-x)$ ，变换一下形式就是 $2\min(x-l, r-x) + \max(x-l, r-x)$ （其实不一定要做这个变换）。

考虑一个 dp： $dp_{i, j}$ 表示第 $i$ 个点向右跑 visit 了 $j$ 条线段时，前的答案。注意这个 dp 状态数是线性的，因为每个点向右一定不会跑过它右边的那个点（一定不优），所以总状态数就是「相邻两点之间线段数的总和」也就是 $m$ 。

我们设第 $i$ 和第 $i-1$ 个点之间一共有 $t$ 条线段。

有个显然的 $\mathcal O(n^2)$ dp：

dp_{i, j} = \min\limits_{k} (dp_{i-1, k} + 2\min(\text{dis}_a, \text{dis}_b) + \max(\text{dis}_a, \text{dis}_b))

其中 $\text{dis}_a, \text{dis}_b$ 分别为第 $i$ 个点向左 visit $t-k$ 条线段的花费，和第 $i$ 个点向右 visit $j$ 条线段的花费。注意到 $\text{dis}_a$ 仅与 $i-1$ 和 $k$ 有关，而 $\text{dis}_b$ 仅与 $i$ 和 $j$ 有关。如果没有 $\min$ 和 $\max$ 的问题，就可以直接优化掉。

可以在存储着 $\text{dis}_a$ 的数组中二分 $\text{dis}_b$ 的位置，此位置之前 $\text{dis}_a \le \text{dis}_b$ ，之后 $\text{dis}_a \ge \text{dis}_b$ ，用前缀 / 后缀 $\min$ 分别计算着两种贡献就可以优化掉 $k$ 的枚举。时间复杂度 $\mathcal O(n \log n)$ 。

细节巨大多。

// 2021.10.19 - 10:38
// Code by LTb
// 午前六時、脇役は最初のページを。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define debug printf("Passing Line %d in function [%s].\n",__LINE__,__FUNCTION__)
#define fi first
#define se second
inline int read(){
    int x=0,f=1;
    char ch='.';
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
inline void chmax(int &x,int y){x=max(x,y);}
inline void chmin(int &x,int y){x=min(x,y);}

const int MOD = 998244353;
inline int add(int x,int y){return(x+y>=MOD)?(x+y-MOD):((x+y<0)?(x+y+MOD):(x+y));}

const int MAXN = 200005;
const int INF = 1e16;
int n, m, mm;
int a[MAXN];
pair<int,int> seg[MAXN];
bool vis[MAXN];
int tot = 0, ans = 0;

bool cmp(pair<int,int> x, pair<int,int> y) {
	if (x.se == y.se) return x.fi > y.fi;
	return x.se < y.se;
}

void readin() {
	n = read(), m = read();
	mm = m;
	for (int i = 1; i <= n; i++)
		a[i] = read();
	sort(a + 1, a + 1 + n);

	tot = 0;
	for (int i = 1; i <= m; i++) {
		int x = read(), y = read();
		int pos = lower_bound(a + 1, a + 1 + n, x) - a;
		if (pos == n + 1 || a[pos] > y) {
			tot++;
			seg[tot].fi = x, seg[tot].se = y;
		}
	}
}

void preparing() {
	m = tot;
	sort(seg + 1, seg + 1 + m, cmp);

	set<int> s;
	for (int i = 1; i <= m; i++) {
		if (seg[i] == seg[i - 1]) continue;
		if (s.lower_bound(seg[i].fi) == s.end()) {
			s.insert(seg[i].fi);
			vis[i] = true;
		}
	}

	tot = 0;
	for (int i = 1; i <= m; i++)
		if (vis[i]) seg[++tot] = seg[i];

	m = tot;
	sort(seg + 1, seg + 1 + m);
}

int le[MAXN], ri[MAXN];
int len[MAXN]; // 每个点后线段个数
vector<int> dis_pre[MAXN], dis_suf[MAXN];
void preparing2() {
	int pos = 0;

	for (int i = 1; i <= n; i++) {
		while (pos < m && seg[pos + 1].se < a[i]) pos++;
		le[i] = pos, ri[i] = pos + 1;
		if (ri[i] > m) ri[i] = 0;
	}

	if (le[1] != 0) ri[0] = 1;
	if (ri[n] != 0) le[n + 1] = m;

	for (int i = 1; i <= n + 1; i++)
		len[i - 1] = max(0ll, le[i] - ri[i - 1] + 1);
	if (le[1] == 0) len[0] = 0;
	if (ri[n] == 0) len[n] = 0;

	dis_pre[0].resize(2), dis_suf[0].resize(2);
	for (int i = 1; i <= n; i++) {
		dis_pre[i].resize(len[i - 1] + 3);
		dis_pre[i][0] = 0;
		for (int j = 1; j <= len[i - 1]; j++) {
			int x = le[i] - j + 1;
			dis_pre[i][j] = a[i] - seg[x].se;
			chmax(dis_pre[i][j], 0ll);
		}

		dis_suf[i].resize(len[i] + 3);
		dis_suf[i][0] = 0;
		for (int j = 1; j <= len[i]; j++) {
			int x = ri[i] + j - 1;
			dis_suf[i][j] = seg[x].fi - a[i];
			chmax(dis_suf[i][j], 0ll);
		}
	}
}

vector<int> dp[MAXN];
int ssuf[MAXN], spre[MAXN], d[MAXN];
void solve() {
	if (m == 0) {
		ans = 0;
		return;
	}

	dp[0].resize(len[0] + 3);
	for (int i = 1; i <= len[0]; i++)
		dp[0][i] = INF;

	for (int i = 0; i <= len[0]; i++)
		d[i] = 0;

	for (int i = 1; i <= n; i++) {
		dp[i].resize(len[i] + 3);
		for (int j = 0; j <= len[i - 1]; j++)
			d[j] = dis_pre[i][j];

		ssuf[len[i - 1] + 1] = INF;
		spre[0] = dp[i - 1][0] + dis_pre[i][len[i - 1]];
		for (int j = 1; j <= len[i - 1]; j++)
			spre[j] = min(spre[j - 1], dp[i - 1][j] + dis_pre[i][len[i - 1] - j]);

		for (int j = len[i - 1]; j >= 0; j--)
			ssuf[j] = min(ssuf[j + 1], dp[i - 1][j] + 2 * dis_pre[i][len[i - 1] - j]);
		
		for (int j = 0; j <= len[i]; j++) {
			int x = lower_bound(d, d + 1 + len[i - 1], dis_suf[i][j]) - d;
			dp[i][j] = INF;
			if (x <= len[i - 1]) chmin(dp[i][j], spre[len[i - 1] - x] + dis_suf[i][j] * 2);
			if (x > 0) chmin(dp[i][j], ssuf[len[i - 1] - x + 1] + dis_suf[i][j]);
		}
	}

	ans = dp[n][len[n]];
}

void clear() {
	for (int i = 0; i <= mm + 2; i++)
		vis[i] = false, seg[i] = {0, 0};

	for (int i = 0; i <= n + 2; i++) {
		dp[i].clear(), dis_pre[i].clear(), dis_suf[i].clear();
		le[i] = ri[i] = len[i] = 0;
	}
	
	for (int i = 0; i <= mm + 2; i++)
		d[i] = ssuf[i] = spre[i] = 0;

	tot = ans = 0;
}

signed main()

{
	int test_case = read();
	while (test_case--) {
		readin();
		preparing();
		preparing2();
		solve();
		cout << ans << endl;
		clear();
	}
	return 0;
}

感谢您的支持，我会继续努力的!