[贺题记录] P5503 [JSOI2016] 灯塔

yiwei / 2023-08-18 / 原文

题外话，以后正经题解放洛谷上，贺题记录这种放博客园吧。

学习自 AThousandSuns 大佬的博客。

题意

给定长度为 $n$ 的数组 $h$ ，对于每一个 $i$ 求出 $p_i$ 使满足： $\forall j,h_j \le h_i + p_i - \sqrt{\left | i - j \right | }$ 。

题解

直接把小于等于号换成等号，自信点，这样就是最优的。再进行一些移项，把 $p_i$ 整理出来，就可以得到一下的式子：

\[p_i = \left \lceil \max_j\left (h_j - h_i + \sqrt{\left | i - j \right |}\right ) \right \rceil \]

拆掉绝对值，先只考虑 $j < i$ 的情况，然后翻转数组再做一遍。

接下来就觉得做不下去了，我们怎么能想到决策单调性的思路呢？

关注到式子中有一个 $\sqrt{i - j}$ ，令 $f_j(i) = \sqrt{i - j}$ ，然后画个图啥的你就会惊奇地发现根号的函数至多只有一个交点，也就是 $f_{j_1}(i)$ 和 $f_{j_2}(i)$ 至多有一个交点！

因为我们是以小取大，也就是用更早的值进行决策，所以可以使用单调队列。因为式子是与 $p_i$ 无关的，所以转移可以按任意顺序进行转移，那么我们就可以进行分治。分治的优点就在于码量小好想，就是有点局限。

定义 $\texttt{solve(l,r,L,R)}$ 表示正在计算区间 $[l,r]$ 的 $p$ 值，并且已知决策点就在 $[L,R]$ 中。

取 $l,r$ 的中点 $mid$ ，求出其决策点 $MID$。那么 $[l,mid - 1] $ 的决策点肯定在 $[L,MID]$ 中，$[mid + 1,r]$ 的决策点肯定在 $[MID,R]$ 中，于是可以进行递归：$\texttt{solve(l,mid-1,L,MID),solve(mid+1,r,MID,R)}$ 。

时间复杂度为 $\mathcal{O}(n\log n)$ 。

注：如果把 $p_i$ 存为实数，然后进行取整，那么决策点就可以看作是唯一的。

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n,a[N];

double ans[N];

double calc(int i,int j) { return sqrt(i - j) + a[j] - a[i]; }	// 计算 

void solve(int l,int r,int L,int R){
	if (l > r) return ;
	int mid = (l + r) >> 1,p = L;								// 二分 
	for (int i = L + 1;i <= min(mid,R);i++)
		if (calc(mid,p) < calc(mid,i)) p = i;					// 计算当前决策点 
	ans[mid] = max(ans[mid],calc(mid,p));						// 更新答案 
	solve(l,mid - 1,L,p); solve(mid + 1,r,p,R);					// 递归求解 
}

int main(){
	scanf("%d",&n);
	for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
	solve(1,n,1,n);												// 正向求解 
	for (int i = 1;i <= n / 2;i++){
		swap(a[i],a[n - i + 1]);
		swap(ans[i],ans[n - i + 1]);
	}
	solve(1,n,1,n);												// 反向求解 
	for (int i = 1;i <= n / 2;i++){
		swap(a[i],a[n - i + 1]);
		swap(ans[i],ans[n - i + 1]);
	}
	for (int i = 1;i <= n;i++) printf("%.0lf\n",ceil(ans[i]));	// 上取整输出答案 
}