1566F - Points Movement - CodeForces Solution

//多测不清空/oh多测不清空/oh 多测不清空/oh 多测不清空/oh 多测不清空/oh 多测不清空/oh 多测不清空/oh
//有个傻逼没有清空线段vector，然后对着样例一直差一 
#include<bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=200010,INF=0x3f3f3f3f3f3f3f3f,mod=1e9+7;
struct node{int l,r;};
int T,n,m,mq;
int a[N],dp[N][2];
vector<node>e;
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read(void){
    int x(0),a(1);char fc(getchar());
    while(!isdigit(fc)){if(fc=='-') a=-1;fc=getchar();}
    while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
    return x*a;
}
inline void print(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
bool cmp(node x,node y){return x.r!=y.r?x.r<y.r:x.l>y.l;}
signed main()
{
	T=read();
	while(T--)
	{
		n=read(),m=read();mq=0;a[0]=-INF,a[n+1]=INF;e.clear();
		for(int i=1;i<=n;i++) a[i]=read();
		sort(a+1,a+1+n);memset(dp,0x3f,sizeof dp);
		for(int i=1,l,r;i<=m;i++)
		{
			l=read(),r=read();
			if(lower_bound(a,a+2+n,l)==upper_bound(a,a+2+n,r)) e.pb({l,r});
		}
		sort(e.begin(),e.end(),cmp);
		for(int i=1;i<(int)e.size();i++)
			if(e[i].l<=e[i-1].l||e[i].r==e[i-1].r)
				e.erase(e.begin()+i),i--;
		dp[0][0]=dp[0][1]=0;vector<int>l,r;
		for(int i=1;i<=n+1;i++)
		{
			l.pb(a[i-1]);
			while(mq<(int)e.size()&&e[mq].r<a[i]) r.pb(e[mq].r),l.pb(e[mq].l),mq++;
			r.pb(a[i]);
			for(int j=0,dl,dr;j<(int)l.size();j++)
				dl=l[j]-a[i-1],dr=a[i]-r[j],
				dp[i][0]=min(dp[i][0],dp[i-1][0]+dl+2*dr),
				dp[i][0]=min(dp[i][0],dp[i-1][1]+2*dl+2*dr),
				dp[i][1]=min(dp[i][1],dp[i-1][0]+dl+dr),
				dp[i][1]=min(dp[i][1],dp[i-1][1]+2*dl+dr);
			l.clear(),r.clear();
		} 
		print(min(dp[n+1][1],dp[n+1][0]));puts("");
	}
	return 0;
}
/*
首先去掉无用区间，那么剩下的图的样子就会变成区间中空的地方夹着一堆点。
因为线段不好考虑，所以考虑点。
dp[i][0/1]表示前i个点且i这个点向左/右移动的最小代价
P.S.:注意下点是可以掉头的，也就是可以先向左再向右！！！！
这种情况可能会更优！ 
发现中间能取出的线段区间显然是单调的，所以每次都把中间那些线段区间取出来就行了。
前后加上两个点的哨兵，也就是防止他走过头了，走到别的点肯定不如直接动那个点。
最后大力方程转移即可。 
*///16446732332333110786