专栏文章

题解：CF515E Drazil and Park

nny_Dacong
CF515E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miop74rg
此快照首次捕获于
2025/12/02 22:53
3 个月前
此快照最后确认于
2025/12/02 22:53
3 个月前
查看原文

思路

首先看到环，考虑断环成链。这样可以方便使用一些处理序列问题的手段。
接着看我们要求的式子：
2(hx+hy)+dist⁡(x,y)2(h_x + h_y) + \operatorname{dist}(x,y)
距离可以试着用前缀和优化。设前缀和数组 ss，sis_i 表示第 ii 棵树与第一棵树的距离。式子可以化为：
2(hx+hy)+sy−sx=2hx+2hy+sy−sx=sy+2hy−sx+2hx=(sy+2hy)−(sx−2hx)\begin{aligned} & 2(h_x + h_y) + s_y - s_x \\ = & 2h_x + 2h_y + s_y - s_x \\ = & s_y + 2h_y - s_x + 2h_x \\ = & (s_y + 2h_y) - (s_x - 2h_x) \end{aligned}
考虑将这个式子最大化。即 (sy+2hy)(s_y + 2h_y) 最大，(sx−2hx)(s_x - 2h_x) 最小。因此维护这两个值，套用 RMQ 的模板即可。
注意：不能选同一棵树
中文翻译得比较随意，没有提出这一点，但英文题面明确说是“Drazil chooses two different trees”。
所以建议做 CF 的题的时候还是看一看英文题面，不要过度依赖翻译。
因此如果最后选的是同一棵树 pp，则还要在 [l∼p−1][l \sim p-1] 中再查询一遍最小值 p1p_1，在 [p+1∼r][p+1 \sim r] 中再查询一遍最大值 p2p_2。
不过最终答案并非就是 [p1∼p2][p_1 \sim p_2]，还有可能是 [p1∼p][p_1 \sim p] 或 [p∼p2][p \sim p_2]。取最大即可。

实现

本题时限 2s，空限 512MB。时间较为宽松但空间对于 ST 表来说并不算大。再考虑到 ST 表边界问题处理起来比较麻烦，所以我们使用线段树维护。
还有一个注意点，我们分析时 sis_i 表示第 ii 棵树与第一棵树的距离，但是题目给的是第 ii 棵树与它后面那棵树的距离，所以读入时 i 要加一。

AC 代码

AC 代码（线段树）CPP
#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long num[200050],sum[200050][2];
long long tree[200050<<2][2];
long long ls(long long x){
	return x<<1;
}
long long rs(long long x){
	return x<<1|1;
}
void push_up(long long p){
	tree[p][0] = sum[tree[ls(p)][0]][0] <= sum[tree[rs(p)][0]][0] ? tree[ls(p)][0] : tree[rs(p)][0];
	tree[p][1] = sum[tree[ls(p)][1]][1] > sum[tree[rs(p)][1]][1] ? tree[ls(p)][1] : tree[rs(p)][1];
	return;
}
void build(long long p,long long pl,long long pr){
	if(pl == pr){
		tree[p][0] = tree[p][1] = pl;
		return;
	}
	long long mid = pl+((pr-pl)>>1);
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
	return;
}
long long query(long long p,long long pl,long long pr,long long l,long long r,long long opt){
	if(l <= pl && pr <= r){
		return tree[p][opt];
	}
	long long mid = pl+((pr-pl)>>1);
	long long res1 = -1,res2 = -1;
	if(l <= mid){
		res1 = query(ls(p),pl,mid,l,r,opt);
	}
	if(mid < r){
		res2 = query(rs(p),mid+1,pr,l,r,opt);
	}
	if((~res1) && (~res2)){
		if(opt == 0){
			return sum[res1][0] <= sum[res2][0] ? res1 : res2;
		}else{
			return sum[res1][1] > sum[res2][1] ? res1 : res2;
		}
	}
	if(~res1){
		return res1;
	}
	return res2;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i = 1; i <= n; i++){
		scanf("%lld",&num[i+1]);
		num[i+n+1] = num[i+1];
	}
	num[1] = num[(n<<1)+1];
	num[(n<<1)+1] = 0;
	for(long long i = 1; i <= (n<<1); i++){
		sum[i][0] = sum[i][1] = sum[i-1][0]+num[i];
	}
	for(long long i = 1; i <= n; i++){
		static long long tp;
		scanf("%lld",&tp);
		tp <<= 1;
		sum[i][1] += tp;
		sum[i][0] -= tp;
		sum[i+n][1] += tp;
		sum[i+n][0] -= tp;
	}
	n <<= 1;
//	for(long long i = 1; i <= n; i++){
//		printf("%4d %4d\n",sum[i][0],sum[i][1]);
//	}
//	puts("------");
	build(1,1,n);
	while(m--){
		static long long tpa,tpb,tpc,tpd,tpe;
		scanf("%lld%lld",&tpa,&tpb);
		tpc = tpd = 0;
		if(tpa <= tpb){
			tpa += (n>>1);
		}
		tpc = query(1,1,n,tpb+1,tpa-1,0);
		tpd = query(1,1,n,tpb+1,tpa-1,1);
		if(tpc == tpd){
			tpe = tpc;
			if(tpe != tpb+1){
				tpc = query(1,1,n,tpb+1,tpe-1,0);
			}
			if(tpe != tpa-1){
				tpd = query(1,1,n,tpe+1,tpa-1,1);
			}
			printf("%lld\n",max({(tpd != tpc ? sum[tpd][1]-sum[tpc][0] : -1),(tpd != tpe ? sum[tpd][1]-sum[tpe][0] : -1),(tpe != tpc ? sum[tpe][1]-sum[tpc][0] : -1)}));
		}else{
			printf("%lld\n",sum[tpd][1]-sum[tpc][0]);
		}
	}
	return 0;
}
AC 记录
没想到我之前做过一遍这道题（不过全忘干净了）。当时用的 ST 表，这里一并贴上来。
AC 代码（ST 表）CPP
#include<bits/stdc++.h>
using namespace std;
long long n,m,logmax;
long long d[200050],num[200050],a[200050],b[200050];
long long Max[200050][20],Min[200050][20];
long long getans(long long l,long long r){
	long long len = log2(r-l+1);
	long long x,y,p,q;
	x = a[Min[l][len]] < a[Min[r-(1<<len)+1][len]] ? Min[l][len] : Min[r-(1<<len)+1][len];
	y = b[Max[l][len]] > b[Max[r-(1<<len)+1][len]] ? Max[l][len] : Max[r-(1<<len)+1][len];
	if(x != y){
		return b[y]-a[x];
	}
	x--;
	if(x-l+1 > 0){
		len = log2(x-l+1);
		p = a[Min[l][len]] < a[Min[x-(1<<len)+1][len]] ? Min[l][len] : Min[x-(1<<len)+1][len];
	}else{
		y++;
		len = log2(r-y+1);
		q = b[Max[y][len]] > b[Max[r-(1<<len)+1][len]] ? Max[y][len] : Max[r-(1<<len)+1][len];
		return b[q]-a[y-1];
	}
	y++;
	if(r-y+1 > 0){
		len = log2(r-y+1);
		q = b[Max[y][len]] > b[Max[r-(1<<len)+1][len]] ? Max[y][len] : Max[r-(1<<len)+1][len];
	}else{
		return b[x+1]-a[p];
	}
	return max(b[x+1]-a[p],b[q]-a[y-1]);
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i = 1; i <= n; i++){
		if(i == n){
			scanf("%lld",&d[1]);
		}else{
			scanf("%lld",&d[i+1]);
		}
	}
	for(long long i = 1; i <= n; i++){
		d[i+n] = d[i];
	}
	d[1] = 0;
	for(long long i = 1; i <= n+n; i++){
		d[i] += d[i-1];
	}
	for(long long i = 1; i <= n; i++){
		scanf("%lld",&num[i]);
		num[i+n] = num[i];
	}
	n <<= 1;
	for(long long i = 1; i <= n; i++){
		a[i] = -((num[i]<<1)-d[i]);
		b[i] = (num[i]<<1)+d[i];
		Min[i][0] = Max[i][0] = i;
	}
	logmax = log2(n);
	for(long long j = 1; j <= logmax; j++){
		for(long long i = 1; i <= n-(1<<j)+1; i++){
			Max[i][j] = b[Max[i][j-1]] > b[Max[i+(1<<(j-1))][j-1]] ? Max[i][j-1] : Max[i+(1<<(j-1))][j-1];
			Min[i][j] = a[Min[i][j-1]] < a[Min[i+(1<<(j-1))][j-1]] ? Min[i][j-1] : Min[i+(1<<(j-1))][j-1];
		}
	}
	while(m--){
		static long long tpa,tpb;
		scanf("%lld%lld",&tpa,&tpb);
		if(tpa <= tpb){
			printf("%lld\n",getans(tpb+1,tpa+n/2-1));
		}else{
			swap(tpa,tpb);
			printf("%lld\n",getans(tpa+1,tpb-1));
		}
	}
	return 0;
}
AC 记录
后记
作者写完本文时已经退役快五个月了。暑假闲来没事上洛谷，发现这道题还在我的补题列表上。为了追忆以前的时光，涨涨咕值，顺手试一试洛谷新的 MD，花了一个下午完成了本题。还好，手没生，也算是一点安慰吧。
Written on July 27th,2025.
——ny_Dacong

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...