自动搬运

查看原文

来自洛谷，原作者为

	daduoli 唯依永恒

搬运于2025-08-24 22:57:57，当前版本为作者最后更新于2024-09-26 19:09:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一蓑烟雨里 春光不觉老

折扇挑珠帘 依稀闻童谣

东风却远送 小径人寥寥

桃花探杯中 谁家女郎笑

—————⌈岁时记⌋

没人发题解，我来水一发。

首先容易想到对于 $D\times A\le B$ 以及 $D\times A>B$ 的情况分开来讨论。

我们先来考虑 $D\times A\le B$ 的情况，这种情况相对好处理很多。

容易知道，我们的图是若干段不施工的区域合并起来的，我们记 $l_i,r_i$ 分别表示第 $i$ 段不施工的区域。

那么我们现在想尽可能的少用操作 $2$，考虑记 $cnt_i$ 表示走到第 $i$ 段至少要用多少次 $2$ 操作，不过需要注意，对于第 $i$ 段而言，可能会出现一段前缀是无法到达的，我们记 $L_i$ 表示第 $i$ 段施工的区域可以被到达的最左边的位置。

然后对于询问 $x$，我们二分出它在哪一段不施工区域中，然后判断一下可达性即可。

这一部分的复杂度是 $O(n\log n)$ 的，也是相对简单的。

接下来考虑 $D\times A>B$ 的情况，这种情况我们需要尽可能多的使用 $2$ 操作。

显然只有在某个 $[L_i,r_i]$ 中的位置才是有用的。

我们考虑动态规划，记 $f_i$ 表示到 $i$ 最多使用多少次操作 $2$。

考虑一个块中的 $f$ 长什么样。

看上去好像是上面这么一回事，$f_{x+D}$ 直接就是 $f_x+1$，但是实际上 $f_{x+D}$ 可以直接从 $f_{x+D-1}$ 转移过来，所以还是非常难做。

我们现在卡住了，没有更多很好的想法了，找点性质。

一个段中前 $D$ 个元素，记他为第 $y$ 个，满足 $f_{1\sim y}=x,f_{y+1\sim D}=x+1$

考虑证明（证明比较感性，不严谨，看看就好了，不看也可以，直接跳了）：

假设 $f_y=x,f_{y+1}=x+k(k>1)$，考虑本质上为什么 $f_y$ 会比 $f_{y+1}$ 少，因为我们 $1$ 操作走了太多了，也就是 $1$ 操作浪费了太多步数。

我们记 $g_y$ 表示 $y$ 执行 $1$ 的次数，$g_{y+1}$ 为 $y+1$ 执行 $y$ 的次数，那么 $f_{y+1}-f_y=k$，也就是说 $g_{y+1}-g_y\ge D$，而倘若浪费的步数比 $y+1$ 的方案多 $D$，那么实际上我们是可以在中途切换到 $y+1$ 的方案，可以看下面这个图。（因为我们想要观察的是 $g_y,g_{y+1}$ 的相对性，所以我们钦定 $g_{y+1}=0$。）

我们倒着看，绿色点表示红色要走到这点才能进行二操作，也就是要浪费绿色点和红色点间距离的 $1$ 操作，那么当浪费的操作 $\ge D$ 时，就可以碰到 $y+1$ 路径上的点了，也就说明按 $y+1$ 那样走是可以更新到我们原本 $y$ 路径上的点的，同时还能少浪费 $D$ 次 $1$ 操作。所以是对的。

也就是一个段前 $D$ 个元素中存在一个分界点使其左边的 $f$ 为 $x$，右边的 $f$ 为 $x+1$。

而因为值只差 $1$，所以我们可以直接令 $f_{x+D}$ 从 $f_x+1$ 转移过去，一定不劣。

所以我们现在对于一个段只需要求前 $D$ 个元素即可，所以实际上我们就是要找到那个分界点，因为有单调性，考虑二分。

而对于一个段的前 $D$ 个元素因为我们不知道他的前驱在哪个元素，所以对于 $i$ 而言，要查询 $i-D$ 在哪个段中。

所以实际上实现出来是一个二分套二分的形式，计算是简单的，对于每个段记 $pos_i$ 表示分界点。

然后查询的话我们是可以做到 $O(\log n)$ 单次查询的。

预处理需要 $O(n\log^2n)$ 的复杂度。

所以这种情况的时间复杂度为 $O(n\log ^2n)$。

总时间复杂度为 $O(n\log^2n)$。

代码写起来没什么细节。

#include<bits/stdc++.h>
#define Yzl unsigned long long
#define mp make_pair
#define pi pair<LL,LL>
#define fi first
#define se second
#define pb emplace_back
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=2e5+10;
const LL inf=1e13;
int n,Q,cnt; 
LL D,A,B;
struct ddl {
	LL l,r;
}a[MAXN],b[MAXN],c[MAXN];
LL f[MAXN];
void sub1() {
	while(Q--) {
		LL x; scanf("%lld",&x);
		LL l=0,r=cnt+1,mid;
		while(l+1<r) { mid=(l+r)/2;
			if(c[mid].r<x) l=mid;
			else r=mid;
		}
		if(c[r].l>x||r==cnt+1) puts("-1");
		else printf("%lld\n",x*A+f[r]*(B-A*D));
	}
}
LL pos[MAXN];
LL erfind(LL x) {
	LL l=0,r=cnt+1,mid;
	while(l+1<r) { mid=(l+r)/2;
		if(c[mid].r<x) l=mid;
		else r=mid;
	}
	if(r==cnt+1||c[r].l>x) x=c[--r].r;
	return f[r]+(x-c[r].l)/D+((x-c[r].l)%D>=pos[r]);
}
void sub2() {
	f[1]=0; pos[1]=D;
	for(int i=2;i<=cnt;++i) {
		LL ls=erfind(c[i].l-D)+1; f[i]=ls;
		LL l=c[i].l,r=min(c[i].r,c[i].l+D-1)+1,mid;
		while(l+1<r) { mid=(l+r)/2;
			if(erfind(mid-D)==ls) r=mid;
			else l=mid;
		} pos[i]=r-c[i].l;
	}
	while(Q--) {
		LL x; scanf("%lld",&x);
		LL l=0,r=cnt+1,mid;
		while(l+1<r) { mid=(l+r)/2;
			if(c[mid].r<x) l=mid;
			else r=mid;
		}
		if(r==cnt+1||c[r].l>x) puts("-1");
		else printf("%lld\n",x*A+(f[r]+(x-c[r].l)/D+((x-c[r].l)%D>=pos[r]))*(B-A*D));
	}
}
int main () {
	scanf("%d%d%lld%lld%lld",&n,&Q,&D,&A,&B);
	for(int i=1;i<=n;++i) {
		scanf("%lld%lld",&a[i].l,&a[i].r);
	} b[++cnt]=(ddl){0,a[1].l-1}; a[n+1].l=inf;
	for(int i=1;i<=n;++i) b[++cnt]=(ddl){a[i].r+1,a[i+1].l-1};
	int CNT=cnt; c[cnt=1]=b[1]; f[1]=0; int pre=0;
	for(int i=1;i<=CNT;++i) {
		while(pre<=cnt&&c[pre].r+D<b[i].l) ++pre;
		if(pre<=cnt&&c[pre].l+D<=b[i].r) {
			c[++cnt]=(ddl){max(b[i].l,c[pre].l+D),b[i].r};
			f[cnt]=f[pre]+1;
		}
	}
	if(D*A<=B) sub1();
	else sub2();
	return 0;
}