「NOIP2012」开车旅行

题意：小 $\text{A}$ 和小 $\text{B}$ 决定利用假期外出旅行，他们将想去的城市从 $1$ 到 $n$ 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 $i$ 的海拔高度为 $h_i$，城市 $i$ 和城市 $j$ 之间的距离 $d_{i,j}$ 恰好是这两个城市海拔高度之差的绝对值，即 $d_{i,j}=|h_i-h_j|$。

旅行过程中，小 $\text{A}$ 和小 $\text{B}$ 轮流开车，第一天小 $\text{A}$ 开车，之后每天轮换一次。他们计划选择一个城市 $s$ 作为起点，一直向东行驶，并且最多行驶 $x$ 公里就结束旅行。

小 $\text{A}$ 和小 $\text{B}$ 的驾驶风格不同，小 $\text{B}$ 总是沿着前进方向选择一个最近的城市作为目的地，而小 $\text{A}$ 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 $x$ 公里，他们就会结束旅行。

在启程之前，小 $\text{A}$ 想知道两个问题：

1、 对于一个给定的 $x=x_0$，从哪一个城市出发，小 $\text{A}$ 开车行驶的路程总数与小 $\text{B}$ 行驶的路程总数的比值最小（如果小 $\text{B}$ 的行驶路程为 $0$，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 $\text{A}$ 开车行驶的路程总数与小 $\text{B}$ 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

2、对任意给定的 $x=x_i$ 和出发城市 $s_i$，小 $\text{A}$ 开车行驶的路程总数以及小 $\text B$ 行驶的路程总数。

这道题居然是倍增。。

我们将城市沿海拔高度排序，因此离城市 $i$ 最近的城市为 $i-1$ 或 $i+1$，同理第二近的城市也可以求出。因此我们可以 $O(1)$ 求出 $\text{A}$ 和 $\text{B}$ 下一个要去的城市。但是它们要一直向东行驶，即向编号大的城市行驶，这时候我们不能判断出下一个要去的城市是否编号比他大，因此我们不能按海拔从低到高来枚举城市。

我们按编号从小到大枚举城市，用 $nexa,nexb$ 数组记录下 $\text{A}$ 和 $\text{B}$ 下一个要去的城市后就删去这个城市。我们需要维护一个快速删除且查询前驱和后继的数据结构，很明显，双向链表能 $O(1)$ 做到这些事。

接着由于 $\text{A,B}$ 轮流开车的模式不变，我们可以采取倍增来加速。设 $f _{i,j,k}$ 表示开车 $2 ^{i}$ 天，从城市 $j$ 出发到达的城市，$k=0$ 表示小 $\text{A}$ 先开车，$k=1$ 则是小 $\text{B}$ 先开车。

同理，我们采取 $disa,disb$ 数组表示这样开车后 $\text{A,B}$ 分别走过的距离。 初始化为 $f _{0,i,0}=nex _{i},f _{0,i,1}=nexb _{i},disa _{0,i,0}=|h _{i}-h _{nexa _{i}}|,disa _{0,i,1}=0$，$disb$ 同理。

接着考虑转移，只有当 $i=1$ 时需要特判，因为此时开车 $2$ 天，前一半和后一半由不同的人开，而当 $i>1$ 时 $2 ^{i-1}$ 是偶数，前一半和后一半都由同一人开。

for(int i=1;i<=18;i++)
	for(int j=1;j<=n;j++)
		for(int k=0;k<=1;k++)
		{
			int l=0;
			if(i==1)
				l=k^1;
			else
				l=k;
			if(f[i-1][j][k])
				f[i][j][k]=f[i-1][f[i-1][j][k]][l];
			if(f[i][j][k])
			{
				disa[i][j][k]=disa[i-1][j][k]+disa[i-1][f[i-1][j][k]][l];
				disb[i][j][k]=disb[i-1][j][k]+disb[i-1][f[i-1][j][k]][l];
			}
        }

接着处理两个询问的共同问题，即从某个城市 $i$，最多走 $j$ 的距离，求出小 $\text{A}$ 和小 $\text{B}$ 走的距离 $da,db$，我们把这个操作叫做 solve。

我们选择将 $i$ 从大到小枚举，倍增往上跳即可。

void solve(int s,long long x)
{
	da=db=0;
	int k=0;
	for(int i=18;i>=0;i--)
		if(f[i][s][k]&&disa[i][s][k]+disb[i][s][k]<=x)
		{
			x-=(disa[i][s][k]+disb[i][s][k]);
			da+=disa[i][s][k];
			db+=disb[i][s][k];
			if(!i)
				k^=1;
			s=f[i][s][k];
		}
}

最后对于第 $1$ 个询问，枚举城市取最大值即可，对于第 $2$ 个询问直接执行 solve 操作即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=100010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,m;
int pos[maxn],nexa[maxn],nexb[maxn];
long long f[21][maxn][2],disa[31][maxn][2],disb[31][maxn][2];
long long x0,ansa=1,ansb,s,da,db;
struct city
{
	int h;
	int id;
	int pre;
	int sub;
}e[maxn];
int cmp(city a,city b)
{
	return a.h<b.h;
}
int check(int a,int b,int x)
{
	if(!a)
		return e[b].id;
	if(!b)
		return e[a].id;
	if(e[x].h-e[a].h<=e[b].h-e[x].h)
		return e[a].id;
	else
		return e[b].id;
}
void remove(int x)
{
	if(e[x].sub)
		e[e[x].sub].pre=e[x].pre;
	if(e[x].pre)
		e[e[x].pre].sub=e[x].sub;
}
void solve(int s,long long x)
{
	da=db=0;
	int k=0;
	for(int i=18;i>=0;i--)
		if(f[i][s][k]&&disa[i][s][k]+disb[i][s][k]<=x)
		{
			x-=(disa[i][s][k]+disb[i][s][k]);
			da+=disa[i][s][k];
			db+=disb[i][s][k];
			if(!i)
				k^=1;
			s=f[i][s][k];
		}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&e[i].h);
		e[i].id=i;
	}
	sort(e+1,e+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		pos[e[i].id]=i;
		e[i].pre=i-1;
		e[i].sub=i+1;
	}
	e[1].pre=e[n].sub=0;
	for(int i=1;i<n;i++)
	{
		int x=pos[i];
		int l=e[x].pre;
		int r=e[x].sub;
		if(l&&(e[x].h-e[l].h<=e[r].h-e[x].h||!r))
		{
			nexb[i]=e[l].id;
			nexa[i]=check(e[l].pre,r,x);
		}
		else
		{
			nexb[i]=e[r].id;
			nexa[i]=check(l,e[r].sub,x);
		}
		remove(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(nexa[i])
		{
			f[0][i][0]=nexa[i];
			disa[0][i][0]=abs(e[pos[i]].h-e[pos[nexa[i]]].h);
			disb[0][i][0]=0;
		}
		if(nexb[i])
		{
			f[0][i][1]=nexb[i];
			disb[0][i][1]=abs(e[pos[i]].h-e[pos[nexb[i]]].h);
			disa[0][i][1]=0;
		}
	}
	for(int i=1;i<=18;i++)
		for(int j=1;j<=n;j++)
			for(int k=0;k<=1;k++)
			{
				int l=0;
				if(i==1)
					l=k^1;
				else
					l=k;
				if(f[i-1][j][k])
					f[i][j][k]=f[i-1][f[i-1][j][k]][l];
				if(f[i][j][k])
				{
					disa[i][j][k]=disa[i-1][j][k]+disa[i-1][f[i-1][j][k]][l];
					disb[i][j][k]=disb[i-1][j][k]+disb[i-1][f[i-1][j][k]][l];
				}
			}
	scanf("%lld",&x0);
	for(int i=1;i<=n;i++)
	{
		solve(i,x0);
		if(!db)
			da=1;
		if(da*ansb<db*ansa||(da*ansb==db*ansa&&e[pos[i]].h>e[pos[s]].h))
		{
			ansa=da;
			ansb=db;
			s=i;
		}
	}
	printf("%lld\n",s);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%lld%lld",&s,&x0);
		solve(s,x0);
		printf("%lld %lld\n",da,db);
	}
	return 0;
}