倍增

原文链接【luogu】https://www.luogu.org/problem/P1081

【题目描述】

小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i的海拔高度为Hi，城市i和城市j之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j]=|Hi−Hj|。

旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶X公里就结束旅行。小A和小B的驾驶风格不同，小B总是沿着前进方向选择一个最近的城市作为目的地，而小A总是沿着前进方向选择第二近的城市作为目的地（本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出X公里，他们就会结束旅行。

在启程之前，小A想知道两个问题：

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

(2)对任意给定的X=Xi和出发城市Si，小A开车行驶的路程总数以及小B行驶的路程总数。

【输入描述】

第一行包含一个整数N，表示城市的数目；

第二行有N个整数，每两个整数之间用一个空格隔开，依次表示城市1到城市N的海拔高度，即H1、H2、······、Hn，且每个Hi都是不同的；

第三行包含一个整数X0；

第四行为一个整数M，表示给定M组Si和Xi；

接下来的M行，每行包含2个整数Si和Xi，表示从城市Si出发，最多行驶Xi公里。

【输出描述】

输出共M+1行；

第一行包含一个整数S0，表示对于给定的X0，从编号为S0的城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小；

接下来的M行，每行包含2个整数，之间用一个空格隔开，依次表示在给定的Si和Xi下小A行驶的里程总数和小B行驶的里程总数。

【样例输入】

样例1：

4

2 3 1 4

3

4

1 3

2 3

3 3

4 3

 

样例2：

10

4 5 6 1 2 3 7 8 9 10

7

10

1 7

2 7

3 7

4 7

5 7

6 7

7 7

8 7

9 7

10 7

【样例输出】

样例1：

1

1 1

2 0

0 0

0 0

 

样例2：

2

3 2

2 4

2 1

2 4

5 1

5 1

2 1

2 0

0 0

0 0

 

 强烈吐槽预处理，还有随时溢出的long long

#include
       
        #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)#define dec(i,l,r) for(int i=l;i>=r;--i)const ll maxn=100005,inf=1e11;using namespace std;template
        
         inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}ll n,pos[maxn],nt[maxn][2];ll f[maxn][28],ff[maxn],dis[maxn][28][2],dd[maxn];double ans,da,db;struct node{    ll val;    int id,lf,rf;    bool operator<(node a)const     {        re val
         
          =dis[a][i][0]+dis[a][i][1])    {        x=x-dis[a][i][0]-dis[a][i][1];        da+=dis[a][i][0];        db+=dis[a][i][1];        a=f[a][i];     }}inline void X0(){    int x,ansp=0;    ans=inf;    //ans为比值    //ansp为最佳位置     rd(x);    inc(i,1,n)    {        da=db=0;        //da为小A走过的路程        //db为小B走过的路程         ask(x,i);        if(db==0)        {            if(ans==inf&&h[pos[i]].val>h[pos[ansp]].val)            ansp=i;        }        else if(da/db
          
           h[pos[ansp]].val)        ans=da/db,ansp=i;    }    printf("%d\n",ansp);}int main(){    freopen("in.txt","r",stdin);     h[0].val=-inf;    rd(n);    inc(i,1,n)    {        rd(h[i].val);        h[i].id=i;    }    h[n].rf=0;    Pre();    Bz();    X0();        int x,opt;    rd(n);    while(n--)    {        da=db=0;        rd(opt),rd(x);        ask(x,opt);        printf("%.0lf %.0lf\n",da,db);    }    re 0;}