记录编号	272576	评测结果	WWWWWWWWWWWWWWWWWWWW
题目名称	[NOIP 2012]开车旅行	最终得分	0
用户昵称	0	是否通过	未通过
代码语言	C++	运行时间	1.120 s
提交时间	2016-06-17 15:23:05	内存使用	51.80 MiB

#include<cstdio>
#include<cstdlib>

#define MAXN 100010
#define ABS(a) ((a)<(0)?(-(a)):(a))
#define d(a,b) (ABS(h[a]-h[b]))

using namespace std;

int root,num,Ans,f[2][MAXN][21][3],n,x[MAXN],h[MAXN],nex[MAXN][1],s1,s2;
double Anst=1000000000.0;

struct at{
	int l,r,x,w,s,rnd;
}tr[100010];

void update(int o){ tr[o].s=tr[tr[o].l].s+tr[tr[o].r].s+1; }

void rt(int &o)
{
	int t=tr[o].l;
	tr[o].l=tr[t].r;
	tr[t].r=o;
	tr[t].s=tr[o].s;
	update(o);
	o=t;
}

void lt(int &o)
{
	int t=tr[o].r;
	tr[o].r=tr[t].l;
	tr[t].l=o;
	tr[t].s=tr[o].s;
	update(o);
	o=t;
}

void insert(int &o,int x,int w)
{
	if(o==0){
		o=++num;
		tr[o].x=x,tr[o].w=w;
		tr[o].rnd=rand();
		update(o);return;
	}
	if(w<tr[o].w){
		insert(tr[o].l,x,w);
		if(tr[tr[o].l].rnd<tr[o].rnd){
			rt(o);
		}
	}else{
		insert(tr[o].r,x,w);
		if(tr[tr[o].r].rnd<tr[o].rnd){
			lt(o);
		}
	}
	update(o);
	return;
}

int findmin(int o,int w)
{
	if(!o)	return 0;
	if(tr[o].w<w){
		int t=findmin(tr[o].r,w);
		if(t!=0)	return t;
		else	return tr[o].x;
	}
	return findmin(tr[o].l,w);
}

int findmax(int o,int w)
{
	if(!o)	return 0;
	if(tr[o].w>w){
		int t=findmax(tr[o].l,w);
		if(t!=0)	return t;
		else	return tr[o].x;
	}
	return findmax(tr[o].l,w);
}

void Work(int x,int s)
{
	int t=0,nex=0;
	s1=0,s2=0;
	for(int i=20;i>=0;i--){
		if(f[0][x][i][1]+f[0][x][i][2]<=s){
			s1+=f[0][x][i][1];
			s2+=f[0][x][i][2];
			x=f[0][x][i][0];
			s-=(f[0][x][i][2]+f[0][x][i][1]);
		}
	}
	if((double)s1/s2<Anst)	Anst=(double)s1/s2,Ans=x;
}

int main()
{
	freopen("drive.in","r",stdin);
	freopen("drive.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&h[i]);
		x[i]=i;
	}
	for(int i=n;i>0;i--){
		int t1,t2,t3,t4;
		t1=findmin(root,h[i]);
		t2=findmax(root,h[i]);
		t3=findmin(root,t1);
		t4=findmax(root,t2);
		insert(root,x[i],h[i]);
		if(d(t1,i)>d(t2,i))	{
			nex[i][0]=t2;
			if(d(t4,i)>d(t1,i))	nex[i][0]=t1;
			else 		nex[i][0]=t4;
		}
		else {
			if(t1!=-1) nex[i][0]=t1;
			if(t2!=-1&&t3!=-1&&d(t3,i)>d(t2,i))	nex[i][0]=t2;
			else		nex[i][0]=t3==-1?0:t3;
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d %d\n",nex[i][0],nex[i][1]);
	}
	for(int i=1;i<=n;i++){
		f[0][i][0][0]=nex[i][0];
		f[0][i][0][1]=d(nex[i][0],i);
		f[1][i][0][0]=nex[i][1];
		f[1][i][0][1]=d(nex[i][1],i);
	}
	for(int i=1;i<=n;i++){
		int nx=f[0][i][0][0];
		f[0][i][1][0]=f[1][nx][0][0];
		f[0][i][1][1]=f[0][i][0][1]+f[1][nx][0][1];
		f[0][i][1][2]=f[0][i][0][2]+f[1][nx][0][2];
	}
	for(int i=1;i<=n;i++){
		for(int k=2;k<=20;k++){
			int nx=f[0][i][k-1][0];
			f[0][i][k][0]=f[0][nx][k-1][0];
			f[0][i][k][1]=f[0][i][k-1][1]+f[0][nx][k-1][1];
			f[0][i][k][2]=f[0][i][k-1][2]+f[0][nx][k-1][2];
		}
	}
	int x0;
	scanf("%d",&x0);
	for(int i=1;i<=n;i++){
		Work(i,x0);
	}
	printf("%d\n",Ans);
	int m=0;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int x,w;
		scanf("%d%d",&x,&w);
		Work(x,w);
		printf("%d %d\n",s1,s2);
	}
	return 0;
}