0x01 写在之前

题目链接:https://www.luogu.org/problemnew/show/P1081

前置技能: ST表 双向链表 倍增 离散化

一看省选/NOI-又是NOIP的题目,我们就大概可以知道这又是一个代码难度较高的高级暴力
▄︻┻┳═一…… ☆<(=￣□￣=!)>

我们将会有以下几种方法优化暴力

• 转化问题
• 倍增 / 二分/ 数论优化 反正我是不会
• 数据结构

那么,先看题目吧

0x02 题目

经过简单的分析题目,我们可以知道,看起来需要预处理了,毕竟看起来并没小于等于$O(m\log(n))$的在线算法

离线的话,倍增和ST表是$O(\log(n))$的

哪我们需要预处理什么呢

• 我们需要知道在每个点时小A小B分别会前往哪里,已经在$2^j$后到达哪里
• 以及到达每一步需要的步数

不太好做?

这个时候就应该祭上离散化,在排序并离散化后我们可以快速的通过双向链表快速的求出小A小B将会前往何处及前往的距离

剩下的东西就是ST表的东西了

0x03 代码

#include <cstdio>
#include <algorithm>

const int N=110000;

inline int Aabs(int a){return a>0?a:0-a;}

struct ci{
    int l,r,id,now,hei;
}c[N];

int n,m,pre,nxt,now,ans,p;
int nid[N],next_a[N],next_b[N],sta[N][25],stb[N][25],f[N][25];
long long x,dis_a,dis_b;
double Min=2147483647;
// helper functions start 

// cmp(ci a,ci b)
// sort helper functions 
// return bool
bool cmp(ci a,ci b){
    return a.hei<b.hei;
}

// fir()
// find tht nearst
// return bool
inline bool fir(){
    if(pre==0) return true;
    if(nxt==0) return false;
    return c[nxt].hei-c[now].hei<c[now].hei-c[pre].hei;
}

// sec(int x,int y)
// find second nearst in a and b
// x > now y < now
// return int 
// - the second nearst's id 
inline int sec(int x,int y){
    if(x==0) return c[y].id;
    if(y==0) return c[x].id;
    if(c[x].hei-c[now].hei<c[now].hei-c[y].hei) return c[x].id;
    else return c[y].id;
}

// get_dis(long long x,int p)
// Get the dis_a ans dis_b
// - x the Max distance
// - p start 
// return void
inline void get_dis(long long x,int p){
    dis_a=dis_b=0;
    for(int j=20;j>=0;j--){
        if(f[p][j]&&(long long)dis_a+dis_b+sta[p][j]+stb[p][j]<=x){
            dis_a+=sta[p][j];
            dis_b+=stb[p][j];
            p=f[p][j];
        }
    }
    if(next_a[p]&&dis_a+dis_b+sta[p][0]<=x) dis_a+=sta[p][0];
}

// helper funtions end

// readin()
// readin
inline void readin(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i].hei);
        c[i].id=i;
    }
}

// init()
// find pre and nxt / Discretization
inline void init(){
    std::sort(c+1,c+n+1,cmp);
    for(int i=1;i<=n;i++){
        nid[c[i].id]=i;
        c[i].l=i-1;
        c[i].r=i+1;
    }
    c[1].l=c[n].r=0;
    for(int i=1;i<=n;i++){
        now=nid[i];pre=c[now].l;nxt=c[now].r;
        if(fir()) next_b[i]=c[nxt].id,next_a[i]=sec(c[nxt].r,pre);
        else next_b[i]=c[pre].id,next_a[i]=sec(nxt,c[pre].l);
        if(pre) c[pre].r=nxt;
        if(nxt) c[nxt].l=pre;
    }
}

// make_st()
// make st table
inline void make_st(){
    for(int i=1;i<=n;i++){
        f[i][0]=next_b[next_a[i]];
        sta[i][0]=Aabs(c[nid[i]].hei-c[nid[next_a[i]]].hei);
        stb[i][0]=Aabs(c[nid[next_a[i]]].hei-c[nid[f[i][0]]].hei);
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];        
            sta[i][j]=sta[i][j-1]+sta[f[i][j-1]][j-1];
            stb[i][j]=stb[i][j-1]+stb[f[i][j-1]][j-1];
        }        
    }
}

// Ans_all()
// find Max of dis_a / dis_b
inline void Ans_all(){
    scanf("%lld",&x);
    for(int i=1;i<=n;i++){
        get_dis(x,i);
        if(Min>(1.0*dis_a/dis_b)){
            Min=1.0*dis_a/dis_b;
            ans=i;
        }
    }
    printf("%d\n",ans);
}

// Ans()
// get ans of all ask
inline void Ans(){
    scanf("%d",&m);
    while(m--){
        scanf("%d%lld",&p,&x);
        get_dis(x,p);
        printf("%lld %lld\n",dis_a,dis_b);
    }
}
int main(){
    readin();
    init();
    make_st();
    Ans_all();
    Ans();
}