2018.11.04 洛谷P1081 開車旅行（倍增）

傳送門

思路簡單碼量超凡？

感覺看完題大家應該都知道是倍增 s b sb sb題了吧。

首先預處理出從每個點出發如果是 A A A走到哪個點，如果是 B B B走到哪個點。

然後利用剛剛預處理出的資訊再預處理從每個點出發 A A A走 2 i 2^i 2i次的距離, B B B走 2 i 2^i 2i次的距離， A , B A,B A,B走 2 i 2^i 2i輪之後到了哪個點。

剩下的詢問就跑倍增就行了。

代碼：

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define fi first
#define se second
using namespace std;
inline int read(){
	int ans=0,w=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans*w;
}
typedef pair<int,int> pii;
const int N=1e5+5;
int Ans=0,ansa=0x3f3f3f3f,ansb=0,x0,n,m,h[N],st[N][21],disa[N][21],disb[N][21],nxta[N],nxtb[N];
struct Node{
	int id,val;
	friend inline bool operator<(const Node&a,const Node&b){return a.val==b.val?h[a.id]<h[b.id]:a.val<b.val;}
};
inline void init(){
	set<pii>S;
	int tot=0;
	Node tmp[5];
	tot=0;
	for(int pos=n;pos;--pos){
		S.insert(pii(h[pos],pos));
		if(pos==n)continue;
		tot=0;
		set<pii>::iterator it=S.find(pii(h[pos],pos));
		if(it!=S.begin()){
			--it,tmp[++tot]=(Node){it->se,h[pos]-it->fi};
			if(it!=S.begin())--it,tmp[++tot]=(Node){it->se,h[pos]-it->fi},++it;
			++it;
		}
		if((++it)!=S.end()){
			tmp[++tot]=(Node){it->se,it->fi-h[pos]};
			if((++it)!=S.end())tmp[++tot]=(Node){it->se,it->fi-h[pos]};
		}
		sort(tmp+1,tmp+tot+1);
		nxtb[pos]=tmp[1].id;
		if(tot^1)nxta[pos]=tmp[2].id;
	}
	for(int i=1;i<=n;++i){
		int p1=nxta[i],p2=nxtb[p1];
		disa[i][0]=p1?abs(h[p1]-h[i]):0,disb[i][0]=p2?abs(h[p1]-h[p2]):0,st[i][0]=p2;
	}
	for(int j=1;j<=20;++j)for(int i=1;i<=n;++i){
		st[i][j]=st[st[i][j-1]][j-1];
		disa[i][j]=disa[i][j-1]+disa[st[i][j-1]][j-1];
		disb[i][j]=disb[i][j-1]+disb[st[i][j-1]][j-1];
	}
}
inline pii solve(int s,int dis){
	pii ret=pii(0,0);
	for(int i=20;~i;--i)if(st[s][i]&&disa[s][i]+disb[s][i]<=dis)dis-=disa[s][i]+disb[s][i],ret.fi+=disa[s][i],ret.se+=disb[s][i],s=st[s][i];
	if(!nxta[s]||abs(h[nxta[s]]-h[s])>dis)return ret;
	return ret.fi+=abs(h[nxta[s]]-h[s]),ret;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)h[i]=read();
	init(),x0=read();
	pii ans;
	for(int i=1;i<=n;++i){
		pii res=solve(i,x0);
		if(!Ans||((long long)ansa*res.se>(long long)ansb*res.fi))ansa=res.fi,ansb=res.se,Ans=i;
	}
	printf("%d\n",Ans);
	for(int i=read(),x,s;i;--i)s=read(),x=read(),ans=solve(s,x),printf("%d %d\n",ans.fi,ans.se);
	return 0;
}