题解

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

对于 A 中的每一个数 Ai，求：

min1≤j<i|Ai−Aj|
以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj 较小的那个。

输入格式
第一行输入整数 n，代表序列长度。

第二行输入 n 个整数A1…An,代表序列的具体数值，数值之间用空格隔开。

输出格式
输出共 n−1 行，每行输出两个整数，数值之间用空格隔开。

分别表示当 i 取 2∼n 时，对应的 min1≤j<i|Ai−Aj| 和 Pi 的值。

数据范围
n≤105,|Ai|≤109
输入样例：
3
1 5 3
输出样例：
4 1
2 1

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

using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;

const int N = 100010;

int n;
set<PII> S;

int main()
{
    cin >> n;

    S.insert({2e18, 0});            //哨兵
    S.insert({-2e18, 0});

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

        if(i > 1)
        {
            auto r = S.lower_bound({a, i});
            auto l = r;
            l --;

            LL al = abs(l->first - a);
            LL ar = abs(r->first - a);
            if(al <= ar) cout << al << ' ' << l->second << endl;
            else cout << ar << ' ' << r->second << endl;
        }

        S.insert({a, i});
    }
    return 0;
}