$set做法$

#include <iostream>
#include <algorithm>
#include <set>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

const LL INF = 4e9;

int n;
set<PLL> s;


int main()
{
    LL x;
    scanf("%d%lld", &n, &x);

    s.insert({INF, n + 1});
    s.insert({-INF, 0});
    s.insert({x, 1});


    for (int i = 2; i <= n; i ++ )
    {
        scanf("%lld", &x);
        LL ans = INF;
        int id = INF;

        auto t = s.upper_bound({x, n + 1});
        t -- ;

        ans = abs(x - t -> first);
        id = t -> second;


        t = s.lower_bound({x, 0});
        if (t -> first - x < ans) //取更小的
        {
            ans = abs(x - t -> first);
            id = t -> second;
        }

        printf("%lld %lld\n", ans, id);
        s.insert({x, i});
    }
    return 0;
}

$链表$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;

const int N = 100010;
const LL INF = 4e9;

int n;
int l[N], r[N], p[N];
PLI a[N], ans[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &a[i].first);
        a[i].second = i;
    }

    sort(a + 1, a + n + 1);

    a[0].first = -INF, a[n + 1].first = INF;
    for (int i = 1; i <= n; i ++ )
    {
        l[i] = i - 1, r[i] = i + 1;
        p[a[i].second] = i;
    }

    for (int i = n; i > 1; i -- )
    {
        int j = p[i]; //对每一个i 找到链表下标
        int left = l[j], right = r[j]; //链表前驱后继
        LL lv = abs(a[j].first - a[left].first);
        LL rv = abs(a[right].first - a[j].first);

        if (lv <= rv) ans[i] = {lv, a[left].second};
        else ans[i] = {rv, a[right].second};

        l[right] = left, r[left] = right;
    }
    for (int i = 2; i <= n; i ++ )
        printf("%d %d\n", ans[i].first, ans[i].second);

    return 0;
}

$单调栈$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;

const int N = 100010;
const LL INF = 4e9;

int n;
int l[N], r[N], p[N];
PLI a[N];
int q[N], tt;


int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &a[i].first);
        a[i].second = i;
    }

    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++ )
        p[a[i].second] = i;

    a[0].first = -INF, a[n + 1].first = -INF;
    q[0] = 0; //哨兵不加也可以 因为 0 n + 1默认是0 第一个算错不影响答案
    for (int i = 1; i <= n; i ++ )
    {
        int v = a[i].second;
        while (a[q[tt]].second >= v) tt -- ;
        l[i] = q[tt];

        q[ ++ tt] = i;
    }

    tt = 0;
    q[0] = 0;
    for (int i = n; i >= 1; i -- )
    {
        int v = a[i].second;
        while (a[q[tt]].second >= v) tt -- ;
        r[i] = q[tt];

        q[ ++ tt] = i;
    }

    for (int i = 2; i <= n; i ++ )
    {
        int j = p[i], left = l[j], right = r[j];
        //printf("%d %d %d\n", j, left, right);
        LL lv = abs(a[j].first - a[left].first);
        LL rv = abs(a[right].first - a[j].first);

        if (lv <= rv) printf("%lld %d\n", lv, a[left].second);
        else printf("%lld %d\n", rv, a[right].second);
    }

    return 0;
}