【题解】邻值查找 [CH1301]

传送门：邻值查找 \([CH1301]\) \([AcWing136]\)

【题目描述】

给定一个长度为 \(n\) 的序列 \(A\)，\(A\) 中的数各不相同。

\(\forall i \in[2,n]\) 求 \(min _{j=1}^{j<i}|A_i−A_j|\) 取得最小值时的 \(j\)。若最小值点不唯一，则选择 \(A_j\) 值较小的那个。

【样例】

样例输入：

3

1 5 3

样例输出：

4 1

2 1

【数据范围】

\(100\%\) \(n \leqslant 10^5,|Ai| \leqslant 10^9\)

---

【分析】

正解链表。像我这种不会链表的蒟蒻就只能写线段树了 \(QAQ\) 。

先离散化，然后维护一颗权值线段树，先把 \(a[1]\) 加进去。

后面对于每个 \(i\)，先查询前面已经有多个比它小的，设为 \(level\)。

此时序列中第 \(level\) 大的数即为 \(a[i]\) 的前驱，第 \(level+1\) 大的即为 \(a[i]\) 的后继（序列中 的数各不相同）。

两者取个最小，若相等则选前驱。

时间复杂度：\(O(nlogn)\) 。

线段树常数比较大，所以有点慢，但也能过。

【Code】

#include<algorithm>

#include<cstdio>

#include<map>

#define pl (p<<1)

#define pr (p<<1|1)

#define mid (L+R>>1)

#define Re register int

using namespace std;

const int N=1e5+3;

int x,y,z,n,k,t,cnt,asw,tmp,root,a[N],b[N];

struct QAQ{int g,l,r;}tr[N<<2];map<int,int>id;

inline void in(Re &x){

    int f=0;x=0;char c=getchar();

    while(c<'0'||c>'9')f|=c=='-',c=getchar();

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

    x=f?-x:x;

}

inline void build(Re p,Re L,Re R){//初始化建树

    tr[p].l=L,tr[p].r=R;

    if(L==R)return;

    build(pl,L,mid),build(pr,mid+1,R);

}

inline void add(Re p,Re x,Re l,Re r){//单点修改

    Re L=tr[p].l,R=tr[p].r;

    if(L==R){++tr[p].g;return;}

    if(x<=mid)add(pl,x,l,r);

    else add(pr,x,l,r);

    tr[p].g=tr[pl].g+tr[pr].g;

}

inline int ask(Re p,Re k){//查询第k大

    if(tr[p].l==tr[p].r)return tr[p].r;

    if(tr[pl].g>=k)return ask(pl,k);

    else return ask(pr,k-tr[pl].g);

}

inline int ask_level(Re p,Re x){//查询小于等于x的个数

    Re L=tr[p].l,R=tr[p].r;

    if(L==R)return tr[p].g;

    if(x<=mid)return ask_level(pl,x);

    else return tr[pl].g+ask_level(pr,x);

}

int main(){

    in(n);

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

    	in(a[i]);

    	if(!id[b[i]=a[i]])id[a[i]]=i;

    }

    sort(b+1,b+n+1),build(1,1,n);

    add(1,lower_bound(b+1,b+n+1,a[1])-b,1,n);

    for(Re i=2;i<=n;++i){

    	k=lower_bound(b+1,b+n+1,a[i])-b;

    	Re level=ask_level(1,k-1);//查询小于a[i]的个数

    	if(level)asw=ask(1,level);//查找第level大（即前驱后继）

    	if(level+1<=i-1){

            tmp=ask(1,level+1);//查找第level+1大（即a[i]后继）

            if(!asw||abs(a[i]-b[asw])>abs(b[tmp]-a[i]))asw=tmp;

            //只有小于才赋值，等于时选择最小的a[j]（即a[i]前驱）

    	}

    	printf("%d %d\n",abs(a[i]-b[asw]),id[b[asw]]);

    	add(1,k,1,n);

    }

}