Codeforces Global Round 16 F | CF1566F Points Movement

https://www.luogu.com.cn/problem/CF1566F

https://codeforces.com/contest/1566/problem/F

这类有关线段的问题我通常都是先观察线段的包含/交对线段是否保留的影响，以约束线段有左右端点的某种性质。

先考虑，A 线段包含 B 线段，那么 A 线段应该舍去，这是显然的，因为只要 B 线段被走过，那么 A 也一定被走过。

那么你考虑做以上操作以及舍弃初始状态下线段内就有点的线段，得到的一定是 线段，点，线段，点 这样交替的形式，且所有线段满足左右端点单不降。

然后你考虑一个点能怎么走。

• 往右。

• 往左。

• 先往左，再往右。

• 先往右，再往左。

注意到点走过的一定路径一定不会有交，有交的话只让一个走就更优。

然后你会发现我们要考虑的仅仅是对于相邻的 2 个点之间的线段由左还是由右走过，所以自然就想到 dp。

考虑 dp 的转移，一个决策点向右的行走可以让下个决策点决定，所以我们仅需要考虑当前决策点向左行走。

注意到，你需要考虑每个点往左走之后是否回到原来的位置，因此，设 \(dp_{i,0/1}\) 表示第 \(i\) 个点，满足在第 \(i\) 个点之前的线段都已经被走过，是否回到原先位置。

显然你枚举中间线段的左右分界线转移即可，注意到，对于先往左，再往右的，等价于回到原来的位置。先往右，再往左的，等价于先往左，然后摊死在那，在下一个决策点计算 2 倍往右的答案。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=(int)(2e5+5);
struct node {
	int l,r;
	node() {
		l=r=0;
	}
	node(int L,int R) {
		l=L; r=R;
	}
}p[N];
bool ok[N];
vector<node>vec[N];
int n,m,a[N],dp[N][2];

bool cmp(const node &x,const node &y) {
	return x.r==y.r?x.l>y.l:x.r<y.r;
}

bool cmp2(const node &x,const node &y) {
	return x.r==y.r?x.l<y.l:x.r<y.r;
}

void sol() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>p[i].l>>p[i].r;
	sort(p+1,p+1+m,cmp); sort(a+1,a+1+n); 
	int mx=-(int)(2e18);
	for(int i=1;i<=m;i++) {
		ok[i]=1;
		if(mx>=p[i].l) {
			ok[i]=0;
		}
		mx=max(mx,p[i].l);
	}
	int tot=0;
	for(int i=1;i<=m;i++) {
		if(ok[i]) {
			int L=lower_bound(a+1,a+1+n,p[i].l)-a,R=upper_bound(a+1,a+1+n,p[i].r)-a-1;
			if(L<=R) continue ;
			vec[L].pb(p[i]);
		}
	}
	for(int i=0;i<=n+1;i++) dp[i][0]=dp[i][1]=(int)(2e18);
	dp[0][0]=dp[0][1]=0;
	a[0]=-(int)(2e18); a[n+1]=(int)(2e18);
	for(int i=1;i<=n+1;i++) {
		int sz=vec[i].size();
//		cout<<i<<'\n';
//		for(auto x:vec[i]) {
//			cout<<x.l<<" , "<<x.r<<'\n';
//		}
		if(!sz) {
			dp[i][0]=dp[i][1]=min(dp[i-1][0],dp[i-1][1]);
			continue ;
		}
		sort(vec[i].begin(),vec[i].end(),cmp2);
		for(int k=0;k<=sz;k++) {
			int qwq=0,qaq=0;
			if(k>0) qwq+=vec[i][k-1].l-a[i-1];
			if(k<sz) qaq+=a[i]-vec[i][k].r;
			dp[i][0]=min(dp[i][0],min(dp[i-1][1]+qwq,qwq*2+dp[i-1][0])+qaq);
			if(!k) {
				dp[i][0]=min(dp[i][0],dp[i-1][0]+qwq+qaq);
			}
			if(k<sz) qaq+=a[i]-vec[i][k].r;
			dp[i][1]=min(dp[i][1],min(dp[i-1][1]+qwq,qwq*2+dp[i-1][0])+qaq);
			if(!k) {
				dp[i][1]=min(dp[i][1],dp[i-1][0]+qwq+qaq);
			}
		}
//		cout<<dp[i][0]<<" "<<dp[i][1]<<'\n';
	}
	cout<<min(dp[n+1][0],dp[n+1][1])<<'\n';
	for(int i=0;i<=n+1;i++) vector<node>().swap(vec[i]);
}

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