Codeforces 1832F - Zombies（wqs 二分）

等价于最大化 \(n\) 对区间的交集之和。而对于每个 \([l_i,r_i)\) 我们肯定会选择与其交集最大的 \([p,p+m)\) 与之匹配，所以我们只用对 \(k\) 个区间进行决策即可。

首先先发现一个东西：存在一种最优解，使得对于每个选择的区间 \([p,p+m)\)，要么有 \(p=l_i\)，要么有 \(p+m=r_i\)，也就是每个选择的区间要么顶着某个输入的区间的左端点，要么顶着某个输入的区间的右端点。感性理解一下是因为对于一个不顶着左右端点的区间，要么向左移动交集呈增大的趋势，要么向右移动呈增大的趋势。

猜测答案具有凸性，因此考虑 wqs 二分。注意到对于一个区间 \([l_i,r_i)\) 而言，与其交集最大的一定所有是 \([p,p+m)\) 中，\(2p+m\) 与 \(l_i+r_i\) 最接近的那个。因此考虑将所有可能选择的 \(p\) 从大到小排序，二分到 \(mid\) 的时候设 \(dp_i\) 表示考虑了前 \(i\) 个关键点，第 \(i\) 个关键点表示的区间被选择时能够得到的最大交集 \(-mid\times\text{选择的区间个数}\)，转移就枚举上一个关键点 \(j\)，然后考虑那些 \(l_t+r_t\in (2p_j+m,2p_i+m]\) 的区间，显然是前一半选择 \(j\)，后一半选择 \(i\)，预处理这个贡献即可。

时间复杂度 \(n^2(\log n+\log V)\)。

const int MAXN=2000;
int n,k,x,m,l[MAXN+5],r[MAXN+5],key[MAXN*2+5],uni[MAXN*2+5],cnt,num,ord[MAXN+5];
ll sum[MAXN*2+5][MAXN+5],cst[MAXN*2+5][MAXN*2+5];
int find_pos(int x){
	int L=1,R=n,p=0;
	while(L<=R){
		int mid=L+R>>1;
		if(l[ord[mid]]+r[ord[mid]]<=x)p=mid,L=mid+1;
		else R=mid-1;
	}return p;
}
ll calc(int id,int l,int r){
	int pl=find_pos(l-1),pr=find_pos(r);
	return sum[id][pr]-sum[id][pl];
}
pair<ll,int>dp[MAXN+5];
pair<ll,int>check(int mid){
	for(int i=1;i<=num;i++)dp[i]=mp(calc(i,0,uni[i]*2+m)-mid,-1);
	for(int i=1;i<=num;i++)for(int j=1;j<i;j++)chkmax(dp[i],mp(dp[j].fi+cst[j][i]-mid,dp[j].se-1));
	pair<ll,int>res=mp(0,0);
	for(int i=1;i<=num;i++)chkmax(res,mp(dp[i].fi+calc(i,uni[i]*2+m+1,2e9),dp[i].se));
	return mp(res.fi,-res.se);
}
int main(){
	scanf("%d%d%d%d",&n,&k,&x,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]),ord[i]=i;
	sort(ord+1,ord+n+1,[&](int x,int y){return l[x]+r[x]<l[y]+r[y];});
	for(int i=1;i<=n;i++)key[++cnt]=min(x-m,l[i]),key[++cnt]=max(0,r[i]-m);
	sort(key+1,key+cnt+1);key[0]=-1;
	for(int i=1;i<=cnt;i++)if(key[i]!=key[i-1])uni[++num]=key[i];
	for(int i=1;i<=num;i++)for(int j=1;j<=n;j++){
		int id=ord[j],L=max(l[id],uni[i]),R=min(r[id],uni[i]+m);
		sum[i][j]=sum[i][j-1]+max(R-L,0);
	}
	for(int i=1;i<=num;i++)for(int j=i+1;j<=num;j++){
		ll L=uni[i]*2+m,R=uni[j]*2+m,mid=L+R>>1;
		cst[i][j]=calc(i,L+1,mid)+calc(j,mid+1,R);
//		printf("cst[%d][%d]=%lld\n",i,j,cst[i][j]);
	}
//	for(int i=1;i<=num;i++)printf("%d%c",uni[i]," \n"[i==num]);
	int L=0,R=1e9,p=0;
	while(L<=R){
		int mid=L+R>>1;
		if(check(mid).se<=k)p=mid,R=mid-1;
		else L=mid+1;
	}pair<ll,int>pp=check(p);ll tot=pp.fi+1ll*p*k,sum=1ll*x*n;
	for(int i=1;i<=n;i++)sum-=r[i]-l[i],sum-=m;sum+=tot;
	printf("%lld\n",sum);
	return 0;
}