70分做法：

先预处理出所有点的最近和次近（O(n^2)一遍就OK）

然后暴力求出每个解（O(nm)）

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

#define inf 0x3fffffff

using namespace std;

int n,x,rech=0x3fffffff,rec,s,m;

double ans=0x3fffffff;

struct Path{int to,weight,to2,weight2;void init(){weight=inf,weight2=inf,to=-1,to2=-1;}}path[100050];

struct Node{int position,height;}node[100050];

bool cmp(Node a,Node b){return a.height<b.height;}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        node[i].position=i;

        scanf("%d",&node[i].height);

    }

    for(int i=1;i<=n;i++){

        path[i].init();

        for(int j=i+1;j<=n;j++){

            if(path[i].weight2>abs(node[j].height-node[i].height)){

                path[i].weight2=abs(node[j].height-node[i].height);

                path[i].to2=node[j].position;

            }

            else if(path[i].weight2==abs(node[j].height-node[i].height)&&node[j].height<node[i].height){

                path[i].to2=node[j].position;

            }

            if(path[i].weight2<path[i].weight){

                swap(path[i].weight2,path[i].weight);

                swap(path[i].to,path[i].to2);

            }

            else if(path[i].weight2==path[i].weight&&node[j].height<node[i].height){

                swap(path[i].to,path[i].to2);

            }

        }

    }

    scanf("%d",&x);

    for(int i=1;i<=n;i++){

        int wei1=0,wei2=0,f=1;

        for(int j=i;;){

            if(f){

                if(wei1+wei2+path[j].weight2<=x)

                    wei2+=path[j].weight2;

                else break;

                j=path[j].to2;

            }

            else{

                if(wei1+wei2+path[j].weight<=x)

                    wei1+=path[j].weight;

                else break;

                j=path[j].to;

            }

            f^=1;

        }

        if(wei1&&(ans>1.0*wei2/wei1||(ans==1.0*wei2/wei1&&rech<node[i].height))){

            ans=1.0*wei2/wei1;

            rec=i;

            rech=node[i].height;

        }

    }

    printf("%d\n",rec);

    scanf("%d",&m);

    for(int i=1;i<=m;i++){

        scanf("%d%d",&s,&x);

        int wei1=0,wei2=0,f=1;

        for(int j=s;;){

            if(f){

                if(wei1+wei2+path[j].weight2<=x)

                    wei2+=path[j].weight2;

                else break;

                j=path[j].to2;

            }

            else{

                if(wei1+wei2+path[j].weight<=x)

                    wei1+=path[j].weight;

                else break;

                j=path[j].to;

            }

            f^=1;

        }

        printf("%d %d\n",wei2,wei1);

    }

}

100分做法：

先用set 从后向前插入 ，取出左边两个点和右边两个点（如果有的话），排个序。

O(nlogn)求出最近和次近。

然后呢 用倍增求距离

g[i][j]表示从i出发走2^j轮到的地方

f[i][j][0]表示从i出发走2^j轮A走了多少

f[i][j][1]表示从i出发走2^j轮B走了多少

预处理出走一轮到哪儿

g[i][0]=edge[edge[i].to2].to;

f[i][0][0]=edge[i].weight2;

f[i][0][1]=edge[edge[i].to2].weight;



倍增就好了…

g[i][j]=g[g[i][j-1]][j-1];

f[i][j][0]=f[g[i][j-1]][j-1][0]+f[i][j-1][0];

f[i][j][1]=f[g[i][j-1]][j-1][1]+f[i][j-1][1];

//By SiriusRen

#include <set>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define int long long

using namespace std;

int n,xx,x,m,g[100050][20],f[100050][20][2],rech,rec;

double ans=0x3fffffff;

struct Node{int height,position;}node[100050];

struct Node2{int height,Short,position;}jy;

struct Edge{int to,to2,weight,weight2;void init(){weight=weight2=0x3fffffff;}}edge[100050];

set<Node>s;set<Node2>p;

bool operator < (Node a,Node b){return a.height<b.height;}

bool operator < (Node2 a,Node2 b){

    if(a.Short!=b.Short)return a.Short<b.Short;

    else return a.height<b.height;

}

void init(){

    for(int i=n;i>=1;i--){

        p.clear();edge[i].init();

        s.insert(node[i]);

        set<Node>::iterator it=s.find(node[i]),it2=it;

        if((++it)!=s.end()){

            jy.height=(*it).height;

            jy.position=(*it).position;

            jy.Short=abs((*it).height-node[i].height);

            p.insert(jy);

        }

        else goto deal1;

        if((++it)!=s.end()){

            jy.height=(*it).height;

            jy.position=(*it).position;

            jy.Short=abs((*it).height-node[i].height);

            p.insert(jy);

        }

        deal1:if(it2==s.begin())goto deal;

        if((--it2)==s.begin()){

            jy.height=(*it2).height;

            jy.position=(*it2).position;

            jy.Short=abs((*it2).height-node[i].height);

            p.insert(jy);

            goto deal;

        }

        else

        {

            jy.height=(*it2).height;

            jy.position=(*it2).position;

            jy.Short=abs((*it2).height-node[i].height);

            p.insert(jy);

        }

        it2--;

        jy.height=(*it2).height;

        jy.position=(*it2).position;

        jy.Short=abs((*it2).height-node[i].height);

        p.insert(jy);

        deal:set<Node2>::iterator itp=p.begin();

        if(itp!=p.end()){

            edge[i].weight=(*itp).Short;

            edge[i].to=(*itp).position;

            if((++itp)!=p.end()){

                edge[i].weight2=(*itp).Short;

                edge[i].to2=(*itp).position;

            }

        }

    }

}

signed main(){

    scanf("%lld",&n);

    for(int i=1;i<=n;i++){

        scanf("%lld",&node[i].height);

        node[i].position=i;

    }

    init();

    for(int i=1;i<=n;i++){

        g[i][0]=edge[edge[i].to2].to;

        f[i][0][0]=edge[i].weight2;

        f[i][0][1]=edge[edge[i].to2].weight;

    }

    for(int j=1;j<=18;j++){

        for(int i=1;i<=n;i++){

            g[i][j]=g[g[i][j-1]][j-1];

            f[i][j][0]=f[g[i][j-1]][j-1][0]+f[i][j-1][0];

            f[i][j][1]=f[g[i][j-1]][j-1][1]+f[i][j-1][1];

        }

    }

    scanf("%lld%lld",&x,&m);

    for(int i=1;i<=n;i++){

        int wei1=0,wei2=0,S=i,temp=x;

        for(int j=17;j>=0;j--){

            if(temp>=f[S][j][0]+f[S][j][1]&&g[S][j]){

                wei1+=f[S][j][0];

                wei2+=f[S][j][1];

                temp=temp-(f[S][j][0]+f[S][j][1]);

                S=g[S][j];

            }

        }

        if(temp>=edge[S].weight2&&edge[S].to2){

            temp-=edge[S].weight2;

            wei1+=edge[S].weight2;

        }

        if(wei2&&(ans>1.0*wei1/wei2||(ans==1.0*wei1/wei2&&rech<node[i].height))){

            rech=node[i].height;

            rec=i;

            ans=1.0*wei1/wei2;

        }

    }

    printf("%lld\n",rec);

    for(int i=1;i<=m;i++){

        scanf("%lld%lld",&xx,&x);

        int wei1=0,wei2=0,S=xx,temp=x;

        for(int j=17;j>=0;j--){

            if(temp>=f[S][j][0]+f[S][j][1]&&g[S][j]){

                wei1+=f[S][j][0];

                wei2+=f[S][j][1];

                temp=temp-(f[S][j][0]+f[S][j][1]);

                S=g[S][j];

            }

        }

        if(temp>=edge[S].weight2&&edge[S].to2){

            temp-=edge[S].weight2;

            wei1+=edge[S].weight2;

        }

        printf("%lld %lld\n",wei1,wei2);

    }

}