题解[CF515E Drazil and Park]

题目描述

Luogu

有(n)个点，每个点有权值(h[i])，第(i)个点与第(j)个点距离为(d[i]),第(1)个点与第(n)个点相邻，(Q)次询问,每次询问给出(1)段区间，求区间内的两个点(i,j)，使(dis(i,j)+2*(h_i+h_j))最大。

题目分析

一环状：考虑断环为链；

二最大化 (dis(i,j)+2(h_i+h_j))

前缀和维护(dis(i,j)=sum_j-sum_i)

式子拆掉

= (sum_j-sum_i+2*h_i+2*h_j)

与(i)相关的放一起，与(j)相关的放一起

=(sum_j+2*h_j-(sum_i-2*h_i))

所以要最大化(sum_j+2*h_j)，最小化(sum_i-2*h_j)

可以用(ST)表、线段树维护区间最值

三注意到(i,j)应为不同的两点，而直接用(ST)表存最值可能会出现两处最值在同一个点上，所以在处理(ST)表的同时要存一下最值的下标。如果在查询时遇到((l,r))最大最小在同一个点(pos)上的情况，处理出((l,pos-1))并((pos+1,r))的最大最小值所在的位置，再与(pos)组合即可。

四记得开(long) (long)

code

#include<bits/stdc++.h>
#define ll long long
#define N (500010)
using namespace std;
ll n,Q,a,b,t=22;
ll d[N],s[N],h[N];
//d:距离 h:如题 s:距离的前缀和
ll st1[N][25],st2[N][25],p1[N][25],p2[N][25];
//st1:最大值  st2:最小值
//p1:最大值的位置 p2:最小值的位置
inline void pre(){
  for(int i=1;i<=n+n;i++){
  	st1[i][0]=s[i]+2*h[i];
  	st2[i][0]=s[i]-2*h[i];
  	p1[i][0]=p2[i][0]=i;
  }
  for(int j=1;j<t;j++){
  	for(int i=1;i<=n+n;i++){
  		if((i+(1<<(j-1)))>n+n) break;
  		st1[i][j]=max(st1[i][j-1],st1[i+(1<<(j-1))][j-1]);
  		if(st1[i][j-1]>st1[i+(1<<(j-1))][j-1]) p1[i][j]=p1[i][j-1];
  		else p1[i][j]=p1[i+(1<<(j-1))][j-1];
  		st2[i][j]=min(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);
  		if(st2[i][j-1]<st2[i+(1<<(j-1))][j-1]) p2[i][j]=p2[i][j-1];
  		else p2[i][j]=p2[i+(1<<(j-1))][j-1];
  	}
  }
  return;
}
//ST表预处理
inline ll askmax(ll l,ll r){
  ll tt=log2(r-l+1);
  if(st1[l][tt]>st1[r-(1<<tt)+1][tt]) return p1[l][tt];
  return p1[r-(1<<tt)+1][tt];
}
inline ll askmin(ll l,ll r){
  ll tt=log2(r-l+1);
  if(st2[l][tt]<st2[r-(1<<tt)+1][tt]) return p2[l][tt];
  return p2[r-(1<<tt)+1][tt];
}
//查询最大最小值所在的位置
inline ll calc(ll x,ll y){return s[x]+2*h[x]-s[y]+2*h[y];}
//计算两点之间的贡献
inline ll ask(ll l,ll r){
  ll pos1=askmax(l,r),pos2=askmin(l,r);
  if(pos1!=pos2) return calc(pos1,pos2);
  else{
  	if(pos1>l&&pos1<r){
  	   ll res1=max(calc(pos1,askmin(l,pos1-1)),calc(pos1,askmin(pos1+1,r)));
  	   ll res2=max(calc(askmax(l,pos1-1),pos1),calc(askmax(pos1+1,r),pos1));
  	   return max(res1,res2);
  	}
  	if(pos1==l&&pos1<r){
  		ll res1=max(calc(askmax(pos1+1,r),pos1),calc(pos1,askmin(pos1+1,r)));
  		return res1;
  	}
  	if(pos1==r&&pos1>l){
  		ll res1=max(calc(askmax(l,pos1-1),pos1),calc(pos1,askmin(l,pos1-1)));
  		return res1;
  	}
  }
  return 0;
}
//如题解
int main(){
  scanf("%lld%lld",&n,&Q);
  for(int i=1;i<=n;i++){
  	scanf("%lld",&d[i]);
  	d[n+i]=d[i];
  	s[i+1]=s[i]+d[i];
  }
  for(int i=n+1;i<=n+n;i++) s[i+1]=s[i]+d[i];
  for(int i=1;i<=n;i++){
  	scanf("%lld",&h[i]);
  	h[i+n]=h[i];
  }
  pre();
  while(Q--){
  	scanf("%lld%lld",&a,&b);
  	if(a>b) printf("%lld
",ask(b+1,a-1));
  	else printf("%lld
",ask(b+1,a-1+n));
  }
  return 0;
}

完结撒花