Uoj#357.【JOI2017春季合宿】Sparklers 题解

题意：

简单来说就是$n$个人跑来跑去，保持烟火不灭所需要的最小速度。
$1\le n\le 10^5,0\le x_i\le 10^9$。

题解：

首先可以想到二分答案。
然后就是一个判定性问题。
我们设$s$为一次传递最多跑的距离。
显然每个时刻点燃过烟火的人可以是一段区间。
如果$[l,r-1]$或者$[l,r+1]$可行区间非空，那么$[l,r]$时传递给的人的可行区间就是$[x_r-(r-l)\times s,x_l+(r-l)\times s]$。（如果区间不存在就是不可行）
可行也就是$x_r-x_l\le 2\times (r-l)\times s$。
设$a_i=x_i-2\times i\times s$，那么$a_r\le a_l$，将每个人抽象为$(i,a_i)$。
那么就是要求一种从$(K,K)$变换到$(1,n)$的方案，使得每一时刻都有左边点在右边上方。
可以分情况讨论一下：
- 如果有一种只往左走的方法可以使左侧变高，走过去显然不会比现在差。（右侧同理）
- 如果两边都不存在变高的方法，那么设当前左侧为$l$，设$l$左侧最低的点为$x$，$x$左侧（包含$x$）最高的点为$y$，那么如果从$l$走到$x$，必然连续地走到$y$。右侧同理。
- 这时我们发现在这种情况下，左边不可能变高，右边不可能变低。
- 所以在两侧都可行的情况下，选择顺序是对结果没有影响的。
- 区间最大最小都可以通过$\rm ST$表实现。
复杂度$O(n\log n\log Ans)$。

代码：

#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 100009
#define mid (l+r>>1)
using namespace std;
int n,K,T,a[N],pre[N],nxt[N],lg[N],bit[20],q[N],top,Min[20][N],Max[20][N];
ll A[N];
int read()
{
	char ch;
	int x=1;
	while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
	int s=ch-'0';
	while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
	return s*x;
}
int get_min(int l,int r)
{
	if (l>r) return 0;
	int k=lg[r-l+1];
	if (A[Min[k][l]]<A[Min[k][r-bit[k]+1]]) return Min[k][l];
	else return Min[k][r-bit[k]+1];
}
int get_max(int l,int r)
{
	if (l>r) return 0;
	int k=lg[r-l+1];
	if (A[Max[k][l]]>A[Max[k][r-bit[k]+1]]) return Max[k][l];
	else return Max[k][r-bit[k]+1];
}
bool check(int v)
{
	int s=v*T;
	for (int i=1;i<=n;i++) A[i]=a[i]-2ll*i*s,Min[0][i]=Max[0][i]=i;
	for (int i=1;i<20;i++)
		for (int j=1;j+bit[i]-1<=n;j++)
		{
			if (A[Min[i-1][j]]<A[Min[i-1][j+bit[i-1]]]) Min[i][j]=Min[i-1][j];
			else Min[i][j]=Min[i-1][j+bit[i-1]];
			if (A[Max[i-1][j]]>A[Max[i-1][j+bit[i-1]]]) Max[i][j]=Max[i-1][j];
			else Max[i][j]=Max[i-1][j+bit[i-1]];
		}
	top=0;
	for (int i=1;i<=n;pre[i]=q[top],q[++top]=i,i++)
		while (top&&A[q[top]]<=A[i]) top--;
	top=0;
	for (int i=n;i;nxt[i]=q[top],q[++top]=i,i--)
		while (top&&A[q[top]]>=A[i]) top--;
	int L=K,R=K;
	while (L>1||R<n)
	{
		if (pre[L]&&A[get_min(pre[L],L-1)]>=A[R]) L=pre[L];
		else if (nxt[R]&&A[get_max(R+1,nxt[R])]<=A[L]) R=nxt[R];
		else
		{
			int x=get_min(1,L-1),y=get_max(R+1,n);
			if (L==1) return A[y]<=A[L];
			if (R==n) return A[x]>=A[R];
			if (A[x]<A[R]||A[y]>A[L]) return 0;
			int xx=get_max(1,x),yy=get_min(y,n);
			if (A[xx]>=A[y]) L=xx;
			else if (A[yy]<=A[x]) R=yy;
			else return 0;
		}
	}
	return 1;
}
int main()
{
	bit[0]=1;
	for (int i=1;i<20;i++) bit[i]=bit[i-1]<<1;
	lg[0]=-1;
	for (int i=1;i<N;i++) lg[i]=lg[i>>1]+1;
	n=read(),K=read(),T=read();
	for (int i=1;i<=n;i++) a[i]=read();
	int l=0,r=1000000000/T+1,ret=0;
	while (l<=r)
	{
		if (check(mid)) ret=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ret);
	return 0;
}